{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Critical Connections in a Network"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #graph #biconnected-component"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #图 #双连通分量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: criticalConnections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查找集群内的关键连接"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>力扣数据中心有&nbsp;<code>n</code>&nbsp;台服务器，分别按从&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n-1</code>&nbsp;的方式进行了编号。它们之间以 <strong>服务器到服务器</strong> 的形式相互连接组成了一个内部集群，连接是无向的。用 &nbsp;<code>connections</code> 表示集群网络，<code>connections[i] = [a, b]</code>&nbsp;表示服务器 <code>a</code>&nbsp;和 <code>b</code>&nbsp;之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。</p>\n",
    "\n",
    "<p><strong>关键连接</strong><em> </em>是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。</p>\n",
    "\n",
    "<p>请你以任意顺序返回该集群内的所有 <strong>关键连接</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/original_images/critical-connections-in-a-network.png\" style=\"height: 205px; width: 200px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]\n",
    "<strong>输出：</strong>[[1,3]]\n",
    "<strong>解释：</strong>[[3,1]] 也是正确的。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 2, connections = [[0,1]]\n",
    "<b>输出：</b>[[0,1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>n - 1 &lt;= connections.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li>不存在重复的连接</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [critical-connections-in-a-network](https://leetcode.cn/problems/critical-connections-in-a-network/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [critical-connections-in-a-network](https://leetcode.cn/problems/critical-connections-in-a-network/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1],[1,2],[2,0],[1,3]]', '2\\n[[0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TarjanCC:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_strongly_connected_component_bfs(n: int, edge: List[List[int]]) -> (int, DefaultDict[int, Set[int]], List[int]):\n",
    "        # 模板：Tarjan求解有向图的强连通分量 edge为有向边要求无自环与重边\n",
    "        dfs_id = 0\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [0] * n\n",
    "        out = []\n",
    "        in_stack = [0] * n\n",
    "        scc_id = 0\n",
    "        scc_node_id = defaultdict(set)\n",
    "        node_scc_id = [-1] * n\n",
    "        parent = [-1]*n\n",
    "        for node in range(n):\n",
    "            if not visit[node]:\n",
    "                stack = [[node, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = 1\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "                        out.append(cur)\n",
    "                        in_stack[cur] = 1\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        if order[cur] == low[cur]:\n",
    "                            while out:\n",
    "                                top = out.pop()\n",
    "                                in_stack[top] = 0\n",
    "                                scc_node_id[scc_id].add(top)\n",
    "                                node_scc_id[top] = scc_id\n",
    "                                if top == cur:\n",
    "                                    break\n",
    "                            scc_id += 1\n",
    "\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            stack.append([nex, 0])\n",
    "                        elif in_stack[nex]:\n",
    "                            low[cur] = low[cur] if low[cur] < order[nex] else order[nex]  # 注意这里是order\n",
    "\n",
    "        # 建立新图\n",
    "        new_dct = [set() for _ in range(scc_id)]\n",
    "        for i in range(n):\n",
    "            for j in edge[i]:\n",
    "                a, b = node_scc_id[i], node_scc_id[j]\n",
    "                if a != b:\n",
    "                    new_dct[b].add(a)\n",
    "        new_degree = [0]*scc_id\n",
    "        for i in range(scc_id):\n",
    "            for j in new_dct[i]:\n",
    "                new_degree[j] += 1\n",
    "        # SCC的数量，分组，每个结点对应的SCC编号\n",
    "        return scc_id, scc_node_id, node_scc_id\n",
    "\n",
    "    @staticmethod\n",
    "    def get_point_doubly_connected_component_bfs(n: int, edge: List[List[int]]) -> Tuple[int, DefaultDict[int, Set[int]], List[Set[int]]]:\n",
    "        # 模板：Tarjan求解无向图的点双连通分量\n",
    "\n",
    "        dfs_id = 0\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [False] * n\n",
    "        out = []\n",
    "        parent = [-1]*n\n",
    "        group_id = 0  # 点双个数\n",
    "        group_node = defaultdict(set)  # 每个点双包含哪些点\n",
    "        node_group_id = [set() for _ in range(n)]  # 每个点属于哪些点双，属于多个点双的点就是割点\n",
    "        child = [0]*n\n",
    "        for node in range(n):\n",
    "            if not visit[node]:\n",
    "                stack = [[node, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = True\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                            # 遇到了割点（有根和非根两种）\n",
    "                            if (parent == -1 and child[cur] > 1) or (parent != -1 and low[nex] >= order[cur]):\n",
    "                                while out:\n",
    "                                    top = out.pop()\n",
    "                                    group_node[group_id].add(top[0])\n",
    "                                    group_node[group_id].add(top[1])\n",
    "                                    node_group_id[top[0]].add(group_id)\n",
    "                                    node_group_id[top[1]].add(group_id)\n",
    "                                    if top == (cur, nex):\n",
    "                                        break\n",
    "                                group_id += 1\n",
    "                            # 我们将深搜时遇到的所有边加入到栈里面，当找到一个割点的时候\n",
    "                            # 就将这个割点往下走到的所有边弹出，而这些边所连接的点就是一个点双\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if nex == parent[cur]:\n",
    "                            continue\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            out.append((cur, nex))\n",
    "                            child[cur] += 1\n",
    "                            stack.append([nex, 0])\n",
    "                        elif low[cur] > order[nex]:\n",
    "                            low[cur] = order[nex]\n",
    "                            out.append((cur, nex))\n",
    "            if out:\n",
    "                while out:\n",
    "                    top = out.pop()\n",
    "                    group_node[group_id].add(top[0])\n",
    "                    group_node[group_id].add(top[1])\n",
    "                    node_group_id[top[0]].add(group_id)\n",
    "                    node_group_id[top[1]].add(group_id)\n",
    "                group_id += 1\n",
    "        # 点双的数量，点双分组节点，每个结点对应的点双编号（割点属于多个点双）\n",
    "        return group_id, group_node, node_group_id\n",
    "\n",
    "    def get_edge_doubly_connected_component_bfs(self, n: int, edge: List[Set[int]]):\n",
    "        # 模板：Tarjan求解无向图的边双连通分量\n",
    "        _, cutting_edges = self.get_cutting_point_and_cutting_edge_bfs(n, [list(e) for e in edge])\n",
    "        for i, j in cutting_edges:\n",
    "            edge[i].discard(j)\n",
    "            edge[j].discard(i)\n",
    "\n",
    "        # 将所有的割边删掉剩下的都是边双连通分量，处理出割边，再对整个无向图进行一次BFS\n",
    "        visit = [0]*n\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if visit[i]:\n",
    "                continue\n",
    "            stack = [i]\n",
    "            visit[i] = 1\n",
    "            cur = [i]\n",
    "            while stack:\n",
    "                x = stack.pop()\n",
    "                for j in edge[x]:\n",
    "                    if not visit[j]:\n",
    "                        visit[j] = 1\n",
    "                        stack.append(j)\n",
    "                        cur.append(j)\n",
    "            ans.append(cur[:])\n",
    "        # 边双的节点分组\n",
    "        return ans\n",
    "\n",
    "    @staticmethod\n",
    "    def get_cutting_point_and_cutting_edge_bfs(n: int, edge: List[List[int]]) -> (Set[int], Set[Tuple[int, int]]):\n",
    "        # 模板：Tarjan求解无向图的割点和割边（也就是桥）\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [0] * n\n",
    "        cutting_point = set()\n",
    "        cutting_edge = []\n",
    "        child = [0]*n\n",
    "        parent = [-1]*n\n",
    "        dfs_id = 0\n",
    "        for i in range(n):\n",
    "            if not visit[i]:\n",
    "                stack = [[i, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = 1\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            pa = parent[cur]\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                            if low[nex] > order[cur]:\n",
    "                                cutting_edge.append((cur, nex) if cur < nex else (nex, cur))\n",
    "                            if pa != -1 and low[nex] >= order[cur]:\n",
    "                                cutting_point.add(cur)\n",
    "                            elif pa == -1 and child[cur] > 1:  # 出发点没有祖先，所以特判一下\n",
    "                                cutting_point.add(cur)\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if nex == parent[cur]:\n",
    "                            continue\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            child[cur] += 1\n",
    "                            stack.append([nex, 0])\n",
    "                        else:\n",
    "                            low[cur] = low[cur] if low[cur] < order[nex] else order[nex]  # 注意这里是order\n",
    "        # 割点和割边\n",
    "        return cutting_point, cutting_edge\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in connections:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        _, ans = TarjanCC().get_cutting_point_and_cutting_edge_bfs(n, dct)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TarjanCC:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def get_strongly_connected_component_bfs(n: int, edge: List[List[int]]) -> (int, DefaultDict[int, Set[int]], List[int]):\n",
    "        # 模板：Tarjan求解有向图的强连通分量 edge为有向边要求无自环与重边\n",
    "        dfs_id = 0\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [0] * n\n",
    "        out = []\n",
    "        in_stack = [0] * n\n",
    "        scc_id = 0\n",
    "        scc_node_id = defaultdict(set)\n",
    "        node_scc_id = [-1] * n\n",
    "        parent = [-1]*n\n",
    "        for node in range(n):\n",
    "            if not visit[node]:\n",
    "                stack = [[node, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = 1\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "                        out.append(cur)\n",
    "                        in_stack[cur] = 1\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        if order[cur] == low[cur]:\n",
    "                            while out:\n",
    "                                top = out.pop()\n",
    "                                in_stack[top] = 0\n",
    "                                scc_node_id[scc_id].add(top)\n",
    "                                node_scc_id[top] = scc_id\n",
    "                                if top == cur:\n",
    "                                    break\n",
    "                            scc_id += 1\n",
    "\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            stack.append([nex, 0])\n",
    "                        elif in_stack[nex]:\n",
    "                            low[cur] = low[cur] if low[cur] < order[nex] else order[nex]  # 注意这里是order\n",
    "\n",
    "        # 建立新图\n",
    "        new_dct = [set() for _ in range(scc_id)]\n",
    "        for i in range(n):\n",
    "            for j in edge[i]:\n",
    "                a, b = node_scc_id[i], node_scc_id[j]\n",
    "                if a != b:\n",
    "                    new_dct[b].add(a)\n",
    "        new_degree = [0]*scc_id\n",
    "        for i in range(scc_id):\n",
    "            for j in new_dct[i]:\n",
    "                new_degree[j] += 1\n",
    "        # SCC的数量，分组，每个结点对应的SCC编号\n",
    "        return scc_id, scc_node_id, node_scc_id\n",
    "\n",
    "    @staticmethod\n",
    "    def get_point_doubly_connected_component_bfs(n: int, edge: List[List[int]]) -> Tuple[int, DefaultDict[int, Set[int]], List[Set[int]]]:\n",
    "        # 模板：Tarjan求解无向图的点双连通分量\n",
    "\n",
    "        dfs_id = 0\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [False] * n\n",
    "        out = []\n",
    "        parent = [-1]*n\n",
    "        group_id = 0  # 点双个数\n",
    "        group_node = defaultdict(set)  # 每个点双包含哪些点\n",
    "        node_group_id = [set() for _ in range(n)]  # 每个点属于哪些点双，属于多个点双的点就是割点\n",
    "        child = [0]*n\n",
    "        for node in range(n):\n",
    "            if not visit[node]:\n",
    "                stack = [[node, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = True\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                            # 遇到了割点（有根和非根两种）\n",
    "                            if (parent == -1 and child[cur] > 1) or (parent != -1 and low[nex] >= order[cur]):\n",
    "                                while out:\n",
    "                                    top = out.pop()\n",
    "                                    group_node[group_id].add(top[0])\n",
    "                                    group_node[group_id].add(top[1])\n",
    "                                    node_group_id[top[0]].add(group_id)\n",
    "                                    node_group_id[top[1]].add(group_id)\n",
    "                                    if top == (cur, nex):\n",
    "                                        break\n",
    "                                group_id += 1\n",
    "                            # 我们将深搜时遇到的所有边加入到栈里面，当找到一个割点的时候\n",
    "                            # 就将这个割点往下走到的所有边弹出，而这些边所连接的点就是一个点双\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if nex == parent[cur]:\n",
    "                            continue\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            out.append((cur, nex))\n",
    "                            child[cur] += 1\n",
    "                            stack.append([nex, 0])\n",
    "                        elif low[cur] > order[nex]:\n",
    "                            low[cur] = order[nex]\n",
    "                            out.append((cur, nex))\n",
    "            if out:\n",
    "                while out:\n",
    "                    top = out.pop()\n",
    "                    group_node[group_id].add(top[0])\n",
    "                    group_node[group_id].add(top[1])\n",
    "                    node_group_id[top[0]].add(group_id)\n",
    "                    node_group_id[top[1]].add(group_id)\n",
    "                group_id += 1\n",
    "        # 点双的数量，点双分组节点，每个结点对应的点双编号（割点属于多个点双）\n",
    "        return group_id, group_node, node_group_id\n",
    "\n",
    "    def get_edge_doubly_connected_component_bfs(self, n: int, edge: List[Set[int]]):\n",
    "        # 模板：Tarjan求解无向图的边双连通分量\n",
    "        _, cutting_edges = self.get_cutting_point_and_cutting_edge_bfs(n, [list(e) for e in edge])\n",
    "        for i, j in cutting_edges:\n",
    "            edge[i].discard(j)\n",
    "            edge[j].discard(i)\n",
    "\n",
    "        # 将所有的割边删掉剩下的都是边双连通分量，处理出割边，再对整个无向图进行一次BFS\n",
    "        visit = [0]*n\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            if visit[i]:\n",
    "                continue\n",
    "            stack = [i]\n",
    "            visit[i] = 1\n",
    "            cur = [i]\n",
    "            while stack:\n",
    "                x = stack.pop()\n",
    "                for j in edge[x]:\n",
    "                    if not visit[j]:\n",
    "                        visit[j] = 1\n",
    "                        stack.append(j)\n",
    "                        cur.append(j)\n",
    "            ans.append(cur[:])\n",
    "        # 边双的节点分组\n",
    "        return ans\n",
    "\n",
    "    @staticmethod\n",
    "    def get_cutting_point_and_cutting_edge_bfs(n: int, edge: List[List[int]]) -> (Set[int], Set[Tuple[int, int]]):\n",
    "        # 模板：Tarjan求解无向图的割点和割边（也就是桥）\n",
    "        order, low = [inf] * n, [inf] * n\n",
    "        visit = [0] * n\n",
    "        cutting_point = set()\n",
    "        cutting_edge = []\n",
    "        child = [0]*n\n",
    "        parent = [-1]*n\n",
    "        dfs_id = 0\n",
    "        for i in range(n):\n",
    "            if not visit[i]:\n",
    "                stack = [[i, 0]]\n",
    "                while stack:\n",
    "                    cur, ind = stack[-1]\n",
    "                    if not visit[cur]:\n",
    "                        visit[cur] = 1\n",
    "                        order[cur] = low[cur] = dfs_id\n",
    "                        dfs_id += 1\n",
    "                    if ind == len(edge[cur]):\n",
    "                        stack.pop()\n",
    "                        cur, nex = parent[cur], cur\n",
    "                        if cur != -1:\n",
    "                            pa = parent[cur]\n",
    "                            low[cur] = low[cur] if low[cur] < low[nex] else low[nex]\n",
    "                            if low[nex] > order[cur]:\n",
    "                                cutting_edge.append((cur, nex) if cur < nex else (nex, cur))\n",
    "                            if pa != -1 and low[nex] >= order[cur]:\n",
    "                                cutting_point.add(cur)\n",
    "                            elif pa == -1 and child[cur] > 1:  # 出发点没有祖先，所以特判一下\n",
    "                                cutting_point.add(cur)\n",
    "                    else:\n",
    "                        nex = edge[cur][ind]\n",
    "                        stack[-1][-1] += 1\n",
    "                        if nex == parent[cur]:\n",
    "                            continue\n",
    "                        if not visit[nex]:\n",
    "                            parent[nex] = cur\n",
    "                            child[cur] += 1\n",
    "                            stack.append([nex, 0])\n",
    "                        else:\n",
    "                            low[cur] = low[cur] if low[cur] < order[nex] else order[nex]  # 注意这里是order\n",
    "        # 割点和割边\n",
    "        return cutting_point, cutting_edge\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in connections:\n",
    "            dct[i].append(j)\n",
    "            dct[j].append(i)\n",
    "        _, edge = TarjanCC().get_cutting_point_and_cutting_edge_bfs(n, dct)\n",
    "        return edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        ret = []\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for u, v in connections:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        f = [0 for _ in range(n)]\n",
    "        l = [0 for _ in range(n)]\n",
    "        timer = 0\n",
    "        def dfs(cur, pre):\n",
    "            nonlocal timer\n",
    "            timer += 1\n",
    "            f[cur] = l[cur] = timer\n",
    "            for nxt in adj[cur]:\n",
    "                if f[nxt] == 0:\n",
    "                    dfs(nxt, cur)\n",
    "                    l[cur] = min(l[cur], l[nxt])\n",
    "                    if f[cur] < l[nxt]:\n",
    "                        ret.append([cur, nxt])\n",
    "                elif nxt != pre:\n",
    "                    l[cur] = min(l[cur], f[nxt])\n",
    "        dfs(0, None)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        if n == 2:\n",
    "            return connections\n",
    "        # 邻接矩阵\n",
    "        adjacent = [[] for i in range(n)]\n",
    "        for u, v in connections:\n",
    "            adjacent[u].append(v)\n",
    "            adjacent[v].append(u)\n",
    "        # 记录有没有被访问过，以及被访问的时间点\n",
    "        time = [-1] * n\n",
    "        rank = 0\n",
    "        # 记录根节点\n",
    "        low = [-1] * n\n",
    "        ret = []\n",
    "\n",
    "        def dfs(u, pa):\n",
    "            nonlocal rank\n",
    "            # 进入此函数，说明u尚未被访问，这是第一次访问\n",
    "            time[u] = rank\n",
    "            low[u] = rank\n",
    "            rank += 1\n",
    "            for v in adjacent[u]:\n",
    "                # v尚未被访问，则下探\n",
    "                if time[v] == -1:\n",
    "                    dfs(v, u)\n",
    "                    low[u] = min(low[u], low[v])\n",
    "                    # 找到桥边：没有形成环的\n",
    "                    if low[v] > time[u]:\n",
    "                        ret.append([u, v])\n",
    "                elif v != pa:\n",
    "                    # 记录环的根节点\n",
    "                    low[u] = min(time[v], low[u])\n",
    "\n",
    "        for u in range(n):\n",
    "            # u尚未被访问\n",
    "            if time[u] == -1:\n",
    "                dfs(u, u)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in connections:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        res = []\n",
    "\n",
    "        T = 0\n",
    "        dfn, low = [0] * n, [0] * n\n",
    "        parent = [-1] * n\n",
    "\n",
    "        stack = [0]  # start node is 0\n",
    "        while stack:\n",
    "            u = stack.pop()\n",
    "\n",
    "            if u >= 0:\n",
    "                if dfn[u]:  # 访问过就不看了\n",
    "                    continue\n",
    "                T += 1\n",
    "                dfn[u] = low[u] = T\n",
    "                stack.append(~u)\n",
    "\n",
    "                for v in g[u]:\n",
    "                    if v == parent[u]: continue\n",
    "\n",
    "                    if dfn[v]:\n",
    "                        low[u] = min(low[u], dfn[v])\n",
    "                    else:\n",
    "                        parent[v] = u\n",
    "                        stack.append(v)\n",
    "            else:  # 回溯到节点 ~u\n",
    "                p, u = parent[~u], ~u\n",
    "                \n",
    "                if p != -1:\n",
    "                    low[p] = min(low[p], low[u])\n",
    "                    if dfn[p] < low[u]:\n",
    "                        res.append([p, u])\n",
    "        \n",
    "        # print(dfn)\n",
    "        # print(low)\n",
    "\n",
    "        # res = []\n",
    "        # for u, v in connections:\n",
    "        #     if dfn[u] < low[v] or dfn[v] < low[u]:\n",
    "        #         res.append([u, v])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in connections:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        res = []\n",
    "\n",
    "        T = 0\n",
    "        dfn, low = [0] * n, [0] * n\n",
    "        parent = [-1] * n\n",
    "\n",
    "        for u in range(n):\n",
    "            if dfn[u]: continue\n",
    "\n",
    "            stack = [u]\n",
    "            while stack:\n",
    "                u = stack.pop()\n",
    "\n",
    "                if u >= 0:\n",
    "                    if dfn[u]:  # 访问过就不看了\n",
    "                        continue\n",
    "                    T += 1\n",
    "                    dfn[u] = low[u] = T\n",
    "                    stack.append(~u)\n",
    "\n",
    "                    for v in g[u]:\n",
    "                        if v == parent[u]: continue\n",
    "\n",
    "                        if dfn[v]:\n",
    "                            if low[u] > dfn[v]:\n",
    "                                low[u] = dfn[v]\n",
    "                        else:\n",
    "                            parent[v] = u\n",
    "                            stack.append(v)\n",
    "                else:  # 回溯到节点 ~u\n",
    "                    p, u = parent[~u], ~u\n",
    "                    if p != -1:\n",
    "                        if low[p] > low[u]:\n",
    "                            low[p] = low[u]\n",
    "                        if dfn[p] < low[u]: # 割边判定\n",
    "                            res.append([p, u])\n",
    "\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        id_list = [-1] * n\n",
    "        id_list[0] = 0\n",
    "        g = [[] for _ in range(n)]\n",
    "        res = []\n",
    "        for i, j in connections:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "\n",
    "        def dfs(cur, node_id, pre):\n",
    "            id_list[cur] = node_id\n",
    "            for ne in g[cur]:\n",
    "                if ne == pre:\n",
    "                    continue\n",
    "                if id_list[ne] == -1:\n",
    "                    dfs(ne, node_id + 1, cur)\n",
    "                if id_list[ne] < id_list[cur]:\n",
    "                    id_list[cur] = id_list[ne]\n",
    "            if node_id == id_list[cur] and pre is not None:\n",
    "                res.append([pre, cur])\n",
    "\n",
    "        dfs(0, 0, None)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        id_list = [-1] * n\n",
    "        id_list[0] = 0\n",
    "        g = [[] for _ in range(n)]\n",
    "        res = []\n",
    "        for i, j in connections:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "\n",
    "        def dfs(cur, node_id, pre) -> int:\n",
    "            id_list[cur] = node_id\n",
    "            for ne in g[cur]:\n",
    "                if ne == pre:\n",
    "                    continue\n",
    "                if id_list[ne] == -1:\n",
    "                    ne_id = dfs(ne, node_id+1, cur)\n",
    "                    if ne_id < id_list[cur]:\n",
    "                        id_list[cur] = ne_id\n",
    "                else:\n",
    "                    if id_list[ne] < id_list[cur]:\n",
    "                        id_list[cur] = id_list[ne]\n",
    "            if node_id == id_list[cur] and pre is not None:\n",
    "                res.append([pre, cur])\n",
    "            return id_list[cur]\n",
    "\n",
    "        dfs(0, 0, None)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for u , v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        times = [0] * n\n",
    "        lows = [0] * n\n",
    "\n",
    "        def targan(node,parent,deep):\n",
    "            times[node] = deep\n",
    "            lows[node] = deep\n",
    "\n",
    "            for nxt in graph[node]:\n",
    "                if times[nxt] == 0:\n",
    "                    targan(nxt,node,deep+1)\n",
    "                    lows[node] = min(lows[node],lows[nxt])\n",
    "                    if times[node] < lows[nxt]:\n",
    "                        res.append([node,nxt])\n",
    "                elif nxt != parent:\n",
    "                    lows[node] = min(lows[node],lows[nxt])\n",
    "        \n",
    "        targan(0,-1,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[\n",
    "        List[int]]:\n",
    "        # 建图\n",
    "        graph = [[] for _ in range(n)]\n",
    "        res = []\n",
    "        for conn in connections:\n",
    "            graph[conn[0]].append(conn[1])\n",
    "            graph[conn[1]].append(conn[0])\n",
    "        \n",
    "        dfn = [0] * n\n",
    "        low = [0] * n\n",
    "\n",
    "        res = []\n",
    "        def tarjan(graph: List[List[int]], cur_node: int, parent_node: int, times: int, dfn: List[int], low: List[int]) -> int:\n",
    "            dfn[cur_node] = low[cur_node] = times\n",
    "            \n",
    "            for child_node in graph[cur_node]:\n",
    "                if not dfn[child_node]:\n",
    "                    times += 1\n",
    "                    low[cur_node] = min(low[cur_node], tarjan(graph, child_node, cur_node, times, dfn, low))\n",
    "                    if low[child_node] > dfn[cur_node]:\n",
    "                        res.append([child_node, cur_node])\n",
    "                elif dfn[child_node] < dfn[cur_node] and child_node != parent_node:\n",
    "                    low[cur_node] = min(low[cur_node], low[child_node])\n",
    "            \n",
    "            return low[cur_node]\n",
    "        \n",
    "        tarjan(graph, 0, 0, 0, dfn, low)\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        #\n",
    "        tid=[-1]*n\n",
    "        g=[[] for _ in range(n)]\n",
    "        for a,b in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        a,b=connections[0]\n",
    "        tid[a]=0\n",
    "        ans=[]\n",
    "        def dfs(root:int,node:int,setid:int)-> int:\n",
    "            if tid[node]==-1:\n",
    "                tid[node]=setid\n",
    "\n",
    "                for c in g[node]:\n",
    "                    if c!=root:\n",
    "                        get=dfs(node,c,setid+1)\n",
    "                        if get<tid[node]:\n",
    "                            tid[node]=get\n",
    "\n",
    "            else:\n",
    "                tid[node]=min(tid[node],setid)\n",
    "\n",
    "          \n",
    "            if tid[node]==setid:\n",
    "                ans.append([root,node])\n",
    "            return tid[node]\n",
    "            \n",
    "        for c in g[a]:\n",
    "            dfs(a,c,1)\n",
    "       \n",
    "        # print(tid)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\r\n",
    "        res = []\r\n",
    "        graph = [[] for _ in range(n)]\r\n",
    "        for edge in connections:\r\n",
    "            graph[edge[0]].append(edge[1])\r\n",
    "            graph[edge[1]].append(edge[0])\r\n",
    "        low = [-1] * n # 每个节点的最小追溯值\r\n",
    "        def Tarjan(prev, cur, index):\r\n",
    "            low[cur] = index\r\n",
    "            dfn = low[cur]\r\n",
    "            for nxt in graph[cur]:\r\n",
    "                if nxt == prev:\r\n",
    "                    continue\r\n",
    "                if low[nxt] == -1:\r\n",
    "                    index += 1 # nxt 从未被搜索过，追溯值+1\r\n",
    "                    Tarjan(cur, nxt, index)\r\n",
    "                if low[nxt] > dfn: # 下一个节点的追溯值比当前节点大\r\n",
    "                    res.append([cur, nxt])\r\n",
    "                low[cur] = min(low[cur], low[nxt])\r\n",
    "        Tarjan(0, 0, 0)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        #解题思路：\n",
    "        #Tarjan算法\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x,y in connections:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        res=[]\n",
    "        # 记录每个节点当前时间戳和最早时间戳\n",
    "        dfn=[-1]*n\n",
    "        low=[-1]*n\n",
    "        # tarjan算法\n",
    "        def tarjan(node,parent,depth):\n",
    "            dfn[node]=depth\n",
    "            low[node]=depth\n",
    "            for nex in graph[node]:\n",
    "                # 下个节点为父节点，跳过\n",
    "                if nex==parent:\n",
    "                    continue\n",
    "                if dfn[nex]==-1:\n",
    "                    tarjan(nex,node,depth+1)\n",
    "                    # 如果当前节点仍然比子节点小，说明找到桥\n",
    "                    if dfn[node]<low[nex]:\n",
    "                        res.append([node,nex])\n",
    "                # 更新当前节点的最小时间戳\n",
    "                low[node]=min(low[node],low[nex])\n",
    "        tarjan(0,-1,0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        #解题思路：\n",
    "        #Tarjan算法：边x->y为桥的条件是：low(y) > dfn(x)\n",
    "        #low:x通过有向边可回溯到的最早时间点\n",
    "        #dfn:DFS中x被访问的时间点\n",
    "\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x,y in connections:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "\n",
    "        res=[]\n",
    "        # 记录每个节点当前时间戳和最早时间戳\n",
    "        dfn=[-1]*n\n",
    "        low=[-1]*n\n",
    "\n",
    "        # tarjan算法\n",
    "        def tarjan(node,parent,depth):\n",
    "            dfn[node]=depth\n",
    "            low[node]=depth\n",
    "            for nex in graph[node]:\n",
    "                # 下个节点为父节点，跳过，即一条边只访问一次\n",
    "                if nex==parent:\n",
    "                    continue\n",
    "                #如果该节点未被访问\n",
    "                if dfn[nex]==-1:\n",
    "                    tarjan(nex,node,depth+1)\n",
    "                    # 如果当前节点仍然比子节点小，说明找到桥\n",
    "                    if low[nex] > dfn[node]:\n",
    "                        res.append([node,nex])\n",
    "                # 更新当前节点的最小时间戳\n",
    "                low[node]=min(low[node],low[nex])\n",
    "        tarjan(0,-1,0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check_graph(edge: List[list], n):\n",
    "    # 访问序号与根节点序号\n",
    "    visit = [0] * n\n",
    "    root = [0] * n\n",
    "    # 割边\n",
    "    cut_edge = []\n",
    "\n",
    "    # 中间变量\n",
    "    stack = set()\n",
    "    index = 1\n",
    "    def tarjan(i, father):\n",
    "        nonlocal index\n",
    "        visit[i] = root[i] = index\n",
    "        index += 1\n",
    "        stack.add(i)\n",
    "        for j in edge[i]:\n",
    "            if j != father:\n",
    "                if not visit[j]:\n",
    "                    tarjan(j, i)\n",
    "                    root[i] = min(root[i], root[j])\n",
    "                    if visit[i] < root[j]:\n",
    "                        cut_edge.append([i, j])\n",
    "                elif j in stack:\n",
    "                    root[i] = min(root[i], visit[j])\n",
    "        return\n",
    "\n",
    "    tarjan(0, -1)\n",
    "    return cut_edge\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            edges[a].append(b)\n",
    "            edges[b].append(a)\n",
    "        cut_edge = check_graph(edges, n)\n",
    "        return cut_edge\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for connection in connections:\n",
    "            graph[connection[0]].append(connection[1])\n",
    "            graph[connection[1]].append(connection[0])\n",
    "\n",
    "        low = [-1] * n  # 记录每个节点的 low 值\n",
    "        ids = [-1] * n  # 记录每个节点的 id 值\n",
    "        parent = [-1] * n\n",
    "        result = []\n",
    "\n",
    "        counter = 0\n",
    "\n",
    "        def dfs(node, parent, counter):\n",
    "            ids[node] = counter\n",
    "            low[node] = counter\n",
    "            counter += 1\n",
    "\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor == parent:\n",
    "                    continue\n",
    "                if ids[neighbor] == -1:\n",
    "                    dfs(neighbor, node, counter)\n",
    "\n",
    "                low[node] = min(low[node], low[neighbor])\n",
    "\n",
    "                if low[neighbor] > ids[node]:\n",
    "                    result.append([node, neighbor])\n",
    "\n",
    "        for i in range(n):\n",
    "            if ids[i] == -1:\n",
    "                dfs(i, -1, 0)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = defaultdict(list)\n",
    "        for connection in connections:\n",
    "            a, b = connection\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        rank = [-2] * n  # 初始化为-2\n",
    "        result = []\n",
    "        depth = 0\n",
    "        \n",
    "        def dfs(node, parent, depth, rank, result, graph):\n",
    "            if rank[node] >= 0:  # 已访问过的节点\n",
    "                return rank[node]\n",
    "            rank[node] = depth\n",
    "            min_back_depth = n\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor == parent:  # 不往回走\n",
    "                    continue\n",
    "                back_depth = dfs(neighbor, node, depth + 1, rank, result, graph)\n",
    "                min_back_depth = min(min_back_depth, back_depth)\n",
    "            if min_back_depth >= depth and parent is not None:\n",
    "                result.append([parent, node])\n",
    "            return min(min_back_depth, rank[node])\n",
    "        \n",
    "        dfs(0, None, 0, rank, result, graph)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in connections:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        INF = float(\"inf\")\n",
    "        dfn = [INF] * n\n",
    "        low = [INF] * n\n",
    "\n",
    "        cur = -1\n",
    "        def tarjan(x, _x):\n",
    "            if _x == -1 or dfn[_x] < dfn[x]:\n",
    "                nonlocal cur\n",
    "                low[x] = dfn[x] = cur + 1\n",
    "                cur += 1\n",
    "                for y in g[x]:\n",
    "                    if y == _x:\n",
    "                        continue\n",
    "                    low[x] = min(low[x], tarjan(y, x))\n",
    "                    low[x] = min(low[x], dfn[y]) \n",
    "            return low[x]\n",
    "\n",
    "        tarjan(0, -1)\n",
    "        ans = []\n",
    "        for x, y in connections:\n",
    "            if low[x] != low[y]:\n",
    "                print(low[x], low[y])\n",
    "                ans.append([x, y])\n",
    "\n",
    "        # print(low)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(u, rank):\n",
    "            if ranks[u]:\n",
    "                return ranks[u]\n",
    "            ranks[u] = rank\n",
    "            min_rank = rank + 1\n",
    "            for v in graph[u]:\n",
    "                if not ranks[v] or ranks[v] != rank - 1:\n",
    "                    rank_v = dfs(v, rank + 1)\n",
    "                    if rank_v <= rank:\n",
    "                        edges.remove((min(u, v), max(u, v)))\n",
    "                    min_rank = min(min_rank, rank_v)\n",
    "            return min_rank\n",
    "        \n",
    "        graph = collections.defaultdict(list)\n",
    "        edges = set()\n",
    "        ranks = [None] * n\n",
    "        \n",
    "        for u, v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "            edges.add((min(u, v), max(u, v)))\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        \n",
    "        return list(edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        ch=[[] for _ in range(n)]\n",
    "        res=[]\n",
    "        dfn=[0]*n;low=[0]*n;cnt=0\n",
    "        def dfs(u,pa):\n",
    "            # pa :起点\n",
    "            nonlocal cnt\n",
    "            cnt+=1\n",
    "            dfn[u]=cnt;low[u]=cnt\n",
    "            for v in ch[u]:\n",
    "                if not dfn[v]:\n",
    "                    dfs(v,u)\n",
    "                    low[u]=min(low[u],low[v])\n",
    "                    tar=(u,v)\n",
    "                    if low[v]>dfn[u]:\n",
    "                        res.append(tar)\n",
    "                elif v!=pa:\n",
    "                    low[u]=min(low[u],dfn[v])\n",
    "\n",
    "        for u,v in connections:\n",
    "            ch[u].append(v)\n",
    "            ch[v].append(u)\n",
    "        for i in range(n):\n",
    "            if not dfn[i]:\n",
    "                dfs(i,i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        path = [[] for i in range(n)]\n",
    "        for x, y in connections:\n",
    "            path[x].append(y)\n",
    "            path[y].append(x)\n",
    "        order = []\n",
    "        def dfs(node, lastnode, order):\n",
    "            visit[node] = 1\n",
    "            toremove = []\n",
    "            for nextNode in path[node]:\n",
    "                if nextNode!=lastnode and visit[nextNode]==0:\n",
    "                    dfs(nextNode, node, order)\n",
    "                    toremove.append(nextNode)\n",
    "            for x in toremove:\n",
    "                path[node].remove(x)\n",
    "            visit[node] = 2\n",
    "            order.append(node)\n",
    "        ans = []\n",
    "        visit = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if visit[i]==0:\n",
    "                dfs(i, -1, order)\n",
    "        visit = [0 for i in range(n)]\n",
    "        order.reverse()\n",
    "        componentsIds = [-1 for i in range(n)]\n",
    "        componentsId = 0\n",
    "        for i in order:\n",
    "            if visit[i]==0:\n",
    "                tmp = []\n",
    "                dfs(i, -1, tmp)\n",
    "                for x in tmp:\n",
    "                    componentsIds[x] = componentsId\n",
    "                componentsId+=1 \n",
    "        for x,y in connections:\n",
    "            if componentsIds[x]!=componentsIds[y]:\n",
    "                ans.append([x,y])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, node, parent, graph, visited, low, disc, ans):\n",
    "        if visited[node]:\n",
    "            # revisited\n",
    "            if parent != -1:\n",
    "                low[parent] = min(low[parent], disc[node])\n",
    "            return\n",
    "        visited[node] = True\n",
    "        disc[node] = disc[parent] + 1 if parent != -1 else 0\n",
    "        low[node] = disc[node]\n",
    "        for nb in graph[node]:\n",
    "            if nb == parent:\n",
    "                continue\n",
    "            self.dfs(nb, node, graph, visited, low, disc, ans)\n",
    "            low[node] = min(low[node], low[nb])\n",
    "        if parent != -1 and low[node] > disc[parent]:\n",
    "            ans.append([parent, node]) \n",
    "        \n",
    "\n",
    "    def make_graph(self, n, connections):\n",
    "        graph = defaultdict(list)\n",
    "        for src, dest in connections:\n",
    "            graph[src].append(dest)\n",
    "            graph[dest].append(src)\n",
    "        return graph\n",
    "\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        low = [0] * (n)\n",
    "        disc = [sys.maxsize] * n\n",
    "        graph = self.make_graph(n, connections)\n",
    "        ans = []\n",
    "        visited = [False] * n\n",
    "        self.dfs(0, -1, graph, visited, low, disc, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        dfn = [0]*n\n",
    "        low = [0]*n\n",
    "        time = 0\n",
    "        res = []\n",
    "        def tarjan(now, parent):\n",
    "            nonlocal time\n",
    "            time += 1\n",
    "            dfn[now] = low[now] = time\n",
    "            for nex in g[now]:\n",
    "                if nex == parent:\n",
    "                    continue\n",
    "                if not dfn[nex]:\n",
    "                    tarjan(nex, now)\n",
    "                    low[now] = min(low[nex], low[now])\n",
    "                    if dfn[now] < low[nex]:\n",
    "                        res.append([now, nex])\n",
    "                else:\n",
    "                    low[now] = min(low[now], dfn[nex])\n",
    "        tarjan(0, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        #审题，关键连接，指的是边，不是点\n",
    "        # #1.暴力方法，\n",
    "        # #依次去除每个点及其相连的边，然后跑一遍dfs，一遍dfs之后，是否vis==n-1,来判断是否联通\n",
    "        # #如果是，该点不是关键链接。o(n2)\n",
    "        # graph=defaultdict(list)\n",
    "        # for i,j in connections:\n",
    "        #     graph[i].append(j)\n",
    "        #     graph[j].append(i)\n",
    "        # def dfs(i):\n",
    "        #     if i not in vis:\n",
    "        #         vis.add(i)\n",
    "        #         for j in graph[i]:\n",
    "        #             dfs(j)\n",
    "\n",
    "        # ans=[]\n",
    "        # for k in range(len(connections)):\n",
    "        #     graph=defaultdict(list)\n",
    "        #     for idx,(i,j) in enumerate(connections):\n",
    "        #         # if i==k or j==k:continue\n",
    "        #         if idx==k:continue\n",
    "        #         graph[i].append(j)\n",
    "        #         graph[j].append(i)\n",
    "        #     if not graph:\n",
    "        #         ans.append(connections[k])#如果都不能建图，比如去掉1，一定是关键连接\n",
    "        #         continue\n",
    "        #     vis=set()\n",
    "        #     # print(list(graph.keys()))\n",
    "        #     start=list(graph.keys())[0]\n",
    "        #     dfs(start)\n",
    "        #     # if len(vis)!=n-1:ans.append(k)\n",
    "        #     if len(vis)!=n:ans.append(connections[k])\n",
    "        # return ans             \n",
    "\n",
    "        #tarjan算法\n",
    "        graph=defaultdict(list)#1.建图\n",
    "        for i,j in connections:\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "        ids=[-1]*n #2.建id\n",
    "        ans=[]\n",
    "        def dfs(cur_node,cur_id,parent):\n",
    "            ids[cur_node]=cur_id#dfs前，先给个id\n",
    "            for j in graph[cur_node]:\n",
    "                if j==parent:continue\n",
    "                elif ids[j]==-1: #相邻不知道，深度取最小\n",
    "                    ids[cur_node]=min(dfs(j,cur_id+1,cur_node),ids[cur_node])\n",
    "                else:#感觉这个ids是深度吧\n",
    "                    ids[cur_node]=min(ids[cur_node],ids[j])\n",
    "            #整理完最终的，id==cur_id\n",
    "            #是环的脑袋\n",
    "            #记得排除特殊情况\n",
    "            if ids[cur_node]==cur_id and cur_node!=0:\n",
    "                ans.append((parent,cur_node))\n",
    "            return ids[cur_node]\n",
    "        dfs(0,0,-1)\n",
    "        return ans         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = defaultdict(list)   \n",
    "        for i, j in connections:\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "        \n",
    "        label = [-1 for i in range(n)]\n",
    "        lowest = [math.inf for i in range(n)]\n",
    "        ret = []\n",
    "        def tarjan(root: int, father: int, id: int):\n",
    "            label[root] = id\n",
    "            lowest[root] = id\n",
    "            # 循环是为了更新自己的lowest[root]\n",
    "            for node in graph[root]:\n",
    "                if node == father:\n",
    "                    continue\n",
    "                # 没访问过？\n",
    "                if label[node] == -1:\n",
    "                    tarjan(node, root, id+1)\n",
    "                lowest[root] = min(lowest[root], lowest[node])\n",
    "                # 都遍历完了之后岂不是需要找关键链接， 只有当自己编号比周围的这个邻居能访问的最小编号还小的时候，就是关键\n",
    "                if label[root] < lowest[node]:\n",
    "                    ret.append((root, node))\n",
    "        \n",
    "        tarjan(0, -1, 0)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        times = 1\n",
    "        dfn = [0] * n\n",
    "        low = [0] * n \n",
    "        fa = [-1] * n\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in connections:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        ans = []\n",
    "\n",
    "        def dfs(x:int):\n",
    "            nonlocal times\n",
    "            dfn[x] = low[x] = times\n",
    "            times += 1\n",
    "            for y in g[x]:\n",
    "                if not dfn[y]:\n",
    "                    fa[y] = x\n",
    "                    dfs(y)\n",
    "                    if low[y] > dfn[x]:\n",
    "                        ans.append([x, y])\n",
    "                    low[x] = min(low[x], low[y])    \n",
    "                elif fa[x] != y:\n",
    "                    low[x] = min(low[x], low[y])\n",
    "        \n",
    "        for i in range(n):\n",
    "            if not dfn[i]:\n",
    "                dfs(i)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "    graph = {}\n",
    "    for con in connections:\n",
    "      if con[0] not in graph:\n",
    "        graph[con[0]] = []\n",
    "      if con[1] not in graph:\n",
    "        graph[con[1]] = []\n",
    "      graph[con[0]].append(con[1])\n",
    "      graph[con[1]].append(con[0])\n",
    "  \n",
    "    timest = [-1] * n\n",
    "  \n",
    "    conn_list = []\n",
    "  \n",
    "    # DFS\n",
    "    def dfs(node, parent, dis_time):\n",
    "      timest[node] = dis_time\n",
    "      current_timest = dis_time\n",
    "      for neighbor in graph[node]:\n",
    "        # 如果邻居是父节点，跳过\n",
    "        if neighbor == parent:\n",
    "          continue\n",
    "        # 如果邻居未访问\n",
    "        if timest[neighbor] == -1:\n",
    "          current_timest = min(current_timest, dfs(neighbor, node, dis_time + 1))\n",
    "        else:\n",
    "          current_timest = min(current_timest, timest[neighbor])\n",
    "  \n",
    "        if timest[neighbor] > dis_time:\n",
    "          conn_list.append([node, neighbor])\n",
    "  \n",
    "      # 更新时间戳\n",
    "      timest[node] = current_timest\n",
    "      return current_timest\n",
    "  \n",
    "    dfs(0, -1, 0)\n",
    "  \n",
    "    return conn_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        ids = [-1] * n \n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for item in connections:\n",
    "            graph[item[0]].append(item[1])\n",
    "            graph[item[1]].append(item[0])\n",
    "        res = []\n",
    "        \n",
    "        def dfs(from_node:int,curr:int,curr_id:int):\n",
    "            ids[curr] = curr_id\n",
    "            neis = graph[curr]\n",
    "            for n in neis:\n",
    "                if n == from_node:\n",
    "                    continue \n",
    "                if ids[n] == -1:\n",
    "                    ids[curr] = min(ids[curr],dfs(curr,n,curr_id + 1))\n",
    "                else:\n",
    "                    ids[curr] = min(ids[curr],ids[n])\n",
    "            \n",
    "            if curr != 0 and ids[curr] == curr_id:\n",
    "                res.append([from_node,curr])\n",
    "\n",
    "            return ids[curr]\n",
    "        \n",
    "        dfs(0,0,1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph=collections.defaultdict(list)\n",
    "        # 建图\n",
    "        for u,v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        res=[]\n",
    "        # 记录每个节点当前时间戳和最早时间戳\n",
    "        dfn=[-1]*n\n",
    "        low=[-1]*n\n",
    "        # tarjan算法\n",
    "        def tarjan(node,parent,depth):\n",
    "            dfn[node]=depth\n",
    "            low[node]=depth\n",
    "            for nex in graph[node]:\n",
    "                # 下个节点为父节点，跳过\n",
    "                if nex==parent:continue\n",
    "                if dfn[nex]==-1:\n",
    "                    tarjan(nex,node,depth+1)\n",
    "                    # 如果当前节点仍然比子节点小，说明找到桥\n",
    "                    if dfn[node]<low[nex]:\n",
    "                        res.append([node,nex])\n",
    "                # 更新当前节点的最小时间戳\n",
    "                low[node]=min(low[node],low[nex])\n",
    "        tarjan(0,-1,0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph=collections.defaultdict(list)\n",
    "        # 建图\n",
    "        for u,v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        res=[]\n",
    "        # 记录每个节点当前时间戳和最早时间戳\n",
    "        dfn=[-1]*n\n",
    "        low=[-1]*n\n",
    "        # tarjan算法\n",
    "        def tarjan(node,parent,depth):\n",
    "            dfn[node]=depth\n",
    "            low[node]=depth\n",
    "            for nex in graph[node]:\n",
    "                # 下个节点为父节点，跳过\n",
    "                if nex==parent:continue\n",
    "                if dfn[nex]==-1:\n",
    "                    tarjan(nex,node,depth+1)\n",
    "                    # 如果当前节点仍然比子节点小，说明找到桥\n",
    "                if dfn[node]<low[nex]:\n",
    "                    res.append([node,nex])\n",
    "                # 更新当前节点的最小时间戳\n",
    "                low[node]=min(low[node],low[nex])\n",
    "        tarjan(0,-1,0)\n",
    "        print(graph)\n",
    "        print(dfn)\n",
    "        print(low)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        def tarjan(x):\n",
    "            dfs[x] = low[x] = self.time\n",
    "            self.time += 1\n",
    "            child = 0\n",
    "            for y in g[x]:\n",
    "                if not dfs[y]:\n",
    "                    child += 1\n",
    "                    f[y] = x\n",
    "                    tarjan(y)\n",
    "                    if f[x] == -1 and child >= 2:\n",
    "                        cut_point.append(x)\n",
    "                    if f[x] != -1 and low[y] >= dfs[x]:\n",
    "                        cut_point.append(x)\n",
    "                    if low[y] > dfs[x]:\n",
    "                        cut_bridge.append([x, y])\n",
    "                    low[x] = min(low[x], low[y])\n",
    "                else:\n",
    "                    if y != f[x]:\n",
    "                        low[x] = min(low[x], low[y])\n",
    "        g = [[] for i in range(n)]\n",
    "        for i, j in connections:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        self.time =  1\n",
    "        cut_point = []\n",
    "        cut_bridge = []\n",
    "        dfs = [0] * n\n",
    "        low = [0] * n\n",
    "\n",
    "        f = [-1] * n\n",
    "        tarjan(0)\n",
    "        return cut_bridge    \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in connections:\n",
    "            graph[a].append(b)   \n",
    "            graph[b].append(a)\n",
    "        dfn = [-1] * n\n",
    "        low = [-1] * n  \n",
    "        point = []\n",
    "        edge = [] \n",
    "        def tarjan(node, par, time):\n",
    "            dfn[node] = time\n",
    "            low[node] = time \n",
    "            child = 0 \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue\n",
    "                if dfn[nei] == - 1:\n",
    "                    child += 1 \n",
    "                    tarjan(nei, node, time + 1)\n",
    "                    if par == - 1 and child > 1 or par != - 1 and low[nei] >= dfn[node]:\n",
    "                        point.append(node) \n",
    "                    if low[nei] > dfn[node]:\n",
    "                        edge.append([node, nei])\n",
    "                    low[node] = min(low[node], low[nei])\n",
    "                else:\n",
    "                    low[node] = min(low[node], dfn[nei])\n",
    "        tarjan(0, - 1, 0)\n",
    "        print(point)\n",
    "        return edge\n",
    "\n",
    "\n",
    "                \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check_graph(edge: List[list], n):\n",
    "    # 访问序号与根节点序号\n",
    "    visit = [0] * n\n",
    "    root = [0] * n\n",
    "    # 割边\n",
    "    cut_edge = []\n",
    "\n",
    "    # 中间变量\n",
    "    stack = set()\n",
    "    index = 1\n",
    "    def tarjan(i, father):\n",
    "        nonlocal index\n",
    "        visit[i] = root[i] = index\n",
    "        index += 1\n",
    "        stack.add(i)\n",
    "        for j in edge[i]:\n",
    "            if j != father:\n",
    "                if not visit[j]:\n",
    "                    tarjan(j, i)\n",
    "                    root[i] = min(root[i], root[j])\n",
    "                    if visit[i] < root[j]:\n",
    "                        cut_edge.append([i, j])\n",
    "                elif j in stack:\n",
    "                    root[i] = min(root[i], visit[j])\n",
    "        return\n",
    "\n",
    "    tarjan(0, -1)\n",
    "    return cut_edge\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            edges[a].append(b)\n",
    "            edges[b].append(a)\n",
    "        cut_edge = check_graph(edges, n)\n",
    "        return cut_edge\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        low = [0] * n; dfn = [0] * n; dfs_clock = 0\n",
    "        isbridge = [False] * n\n",
    "        G = [[] for j in range(n)]\n",
    "        father = [0] * n\n",
    "\n",
    "        def tarjan(u, fa):\n",
    "            nonlocal dfs_clock\n",
    "            father[u] = fa\n",
    "            low[u] = dfn[u] = dfs_clock\n",
    "            dfs_clock = dfs_clock + 1\n",
    "            for i in range(0, len(G[u])):\n",
    "                v = G[u][i]\n",
    "                if dfn[v] == False:\n",
    "                    tarjan(v, u)\n",
    "                    low[u] = min(low[u], low[v])\n",
    "                    if low[v] > dfn[u]:\n",
    "                        isbridge[v] = True\n",
    "                elif dfn[v] < dfn[u] and v != fa:\n",
    "                    low[u] = min(low[u], dfn[v])\n",
    "    \n",
    "        for a,b in connections:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        tarjan(0,-1)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if isbridge[i]: res.append([i,father[i]])\n",
    "        # print(isbridge, father)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        low = [0] * n; dfn = [0] * n; dfs_clock = 0\n",
    "        isbridge = [False] * n\n",
    "        G = [[] for j in range(n)]\n",
    "        cnt_bridge = 0\n",
    "        father = [0] * n\n",
    "\n",
    "        def tarjan(u, fa):\n",
    "            nonlocal dfs_clock, cnt_bridge\n",
    "            father[u] = fa\n",
    "            low[u] = dfn[u] = dfs_clock\n",
    "            dfs_clock = dfs_clock + 1\n",
    "            for i in range(0, len(G[u])):\n",
    "                v = G[u][i]\n",
    "                if dfn[v] == False:\n",
    "                    tarjan(v, u)\n",
    "                    low[u] = min(low[u], low[v])\n",
    "                    if low[v] > dfn[u]:\n",
    "                        isbridge[v] = True\n",
    "                        cnt_bridge = cnt_bridge + 1\n",
    "                elif dfn[v] < dfn[u] and v != fa:\n",
    "                    low[u] = min(low[u], dfn[v])\n",
    "    \n",
    "        for a,b in connections:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        tarjan(0,-1)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if isbridge[i]: res.append([i,father[i]])\n",
    "        # print(isbridge, father)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        low = [0] * n; dfn = [0] * n; dfs_clock = 0\n",
    "        isbridge = [False] * n\n",
    "        G = [[] for j in range(n)]\n",
    "        cnt_bridge = 0\n",
    "        father = [0] * n\n",
    "\n",
    "        def tarjan(u, fa):\n",
    "            nonlocal dfs_clock, cnt_bridge\n",
    "            father[u] = fa\n",
    "            low[u] = dfn[u] = dfs_clock\n",
    "            dfs_clock = dfs_clock + 1\n",
    "            for i in range(0, len(G[u])):\n",
    "                v = G[u][i]\n",
    "                if dfn[v] == False:\n",
    "                    tarjan(v, u)\n",
    "                    low[u] = min(low[u], low[v])\n",
    "                    if low[v] > dfn[u]:\n",
    "                        isbridge[v] = True\n",
    "                        cnt_bridge = cnt_bridge + 1\n",
    "                elif dfn[v] < dfn[u] and v != fa:\n",
    "                    low[u] = min(low[u], dfn[v])\n",
    "    \n",
    "        for a,b in connections:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        tarjan(0,-1)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if isbridge[i]: res.append([i,father[i]])\n",
    "        print(isbridge, father)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        def tarjan(cur, prev, time):\n",
    "            self.time += 1\n",
    "            dfn[cur]=low[cur] = self.time\n",
    "            for next in link[cur]:\n",
    "                if next != prev:\n",
    "                    if dfn[next] == 0:\n",
    "                        tarjan(next, cur, time)\n",
    "                        low[cur] = min(low[cur], low[next])\n",
    "                        if low[next] > dfn[cur]:\n",
    "                            cutting_edges.append([cur, next])\n",
    "                    else:\n",
    "                        low[cur] = min(low[cur], dfn[next])\n",
    "        link, dfn, low =defaultdict(list), [0]*n, [0]*n# link为字典邻接表\n",
    "        self.time = 0\n",
    "        for a, b in connections:\n",
    "            link[a].append(b)#无向图\n",
    "            link[b].append(a)#无向图\n",
    "        cutting_edges =[]\n",
    "        tarjan(connections[0][0], None,time)\n",
    "        return cutting_edges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        def tarjan (cur,prev,time):\n",
    "            self.time += 1\n",
    "            dfn[cur] = low[cur] = self.time\n",
    "            for next in link[cur]:\n",
    "                if next != prev:\n",
    "                    if dfn[next] == 0:\n",
    "                        tarjan(next,cur,time)\n",
    "                        low[cur] = min(low[cur],low[next])\n",
    "                        if low[next] > dfn[cur]:\n",
    "                            cutting_eages.append([cur,next])\n",
    "                    else:\n",
    "                        low[cur] = min(low[cur],dfn[next])\n",
    "        link,dfn,low = defaultdict(list),[0]*n,[0]*n\n",
    "        self.time = 0\n",
    "        for a,b in connections:\n",
    "            link[a].append(b)\n",
    "            link[b].append(a)\n",
    "        cutting_eages = []\n",
    "        tarjan(connections[0][0],None,time)\n",
    "        return cutting_eages"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for conn in connections:\n",
    "            graph[conn[0]].append(conn[1])\n",
    "            graph[conn[1]].append(conn[0])\n",
    "\n",
    "        # 将边排序\n",
    "        connections = set(map(tuple, (map(sorted, connections))))\n",
    "        # DFS 访问每个节点的深度，只有访问过的路径有深度，初始化为 -1\n",
    "        rank = [-1] * n\n",
    "\n",
    "        def dfs(node, parent, depth):\n",
    "            # 如果已经访问过该边，则已经记录了rank, 通过parent和rank避免死循环\n",
    "            if rank[node] != -1:\n",
    "                return rank[node]\n",
    "\n",
    "            # 记录当前 node 的 depth\n",
    "            rank[node] = depth\n",
    "\n",
    "            min_depth = n\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor == parent: continue\n",
    "\n",
    "                neighbor_depth = dfs(neighbor, node, depth + 1)\n",
    "                if neighbor_depth <= depth:\n",
    "                    connections.discard(tuple(sorted([node, neighbor])))\n",
    "\n",
    "                # 环点的最小深度也要记录下来，以便把整个环去掉\n",
    "                min_depth = min(min_depth, neighbor_depth)\n",
    "            return min_depth\n",
    "\n",
    "        dfs(0, -1, 0)\n",
    "        return list(map(list, connections))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for conn in connections:\n",
    "            graph[conn[0]].append(conn[1])\n",
    "            graph[conn[1]].append(conn[0])\n",
    "\n",
    "        connections = set(map(tuple, (map(sorted, connections))))\n",
    "        rank = [-1] * n\n",
    "\n",
    "        def dfs(node, parent, depth):\n",
    "            if rank[node] >= 0:\n",
    "                return rank[node]\n",
    "            rank[node] = depth\n",
    "            min_depth = n\n",
    "            for v in graph[node]:\n",
    "                if v == parent:\n",
    "                    continue\n",
    "                back_depth = dfs(v, node, depth+1)\n",
    "                if back_depth <= depth:\n",
    "                    connections.discard(tuple(sorted((node, v))))\n",
    "                min_depth = min(min_depth, back_depth)\n",
    "                \n",
    "            return min_depth\n",
    "        dfs(0, -1, 0)\n",
    "        return list(connections)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "        \n",
    "        low = [-1] * n\n",
    "        disc = [-1] * n\n",
    "        visited = [False] * n\n",
    "        result = []\n",
    "        time = 0\n",
    "        \n",
    "        def dfs(node, parent):\n",
    "            nonlocal time\n",
    "            visited[node] = True\n",
    "            disc[node] = time\n",
    "            low[node] = time\n",
    "            time += 1\n",
    "            \n",
    "            for neighbor in graph[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    dfs(neighbor, node)\n",
    "                    low[node] = min(low[node], low[neighbor])\n",
    "                    if low[neighbor] > disc[node]:\n",
    "                        result.append([node, neighbor])\n",
    "                elif neighbor != parent:\n",
    "                    low[node] = min(low[node], disc[neighbor])\n",
    "        \n",
    "        dfs(0, -1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        g = defaultdict(list) \n",
    "        for a,b in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a) \n",
    "        \n",
    "        dfn = [0] * n \n",
    "        low = [0] * n \n",
    "        vis = [0] * n \n",
    "        cnt = 0 \n",
    "        ans = []\n",
    "        def dfs(u, fa):\n",
    "            nonlocal cnt \n",
    "            cnt += 1\n",
    "            dfn[u] = low[u] = cnt\n",
    "            vis[u] = 1 \n",
    "            for v in g[u]:\n",
    "                if not vis[v]:\n",
    "                    dfs(v, u)\n",
    "                    if low[v] > dfn[u]:\n",
    "                        ans.append([u,v])\n",
    "                    low[u] = min(low[u],low[v])\n",
    "                elif v != fa:\n",
    "                    low[u] = min(low[u], dfn[v])\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                dfs(i, i) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for conn in connections:\n",
    "            graph[conn[0]].append(conn[1])\n",
    "            graph[conn[1]].append(conn[0])\n",
    "        connections = set(map(tuple, (map(sorted, connections))))\n",
    "        rank = [-2] * n\n",
    "        def dfs(node, depth):\n",
    "            if rank[node] >= 0:\n",
    "                return rank[node]\n",
    "            rank[node] = depth \n",
    "            min_back_depth = n \n",
    "            for neighbor in graph[node]:\n",
    "                if rank[neighbor] == depth - 1:\n",
    "                    continue \n",
    "                back_depth = dfs(neighbor, depth + 1)\n",
    "                if back_depth <= depth:\n",
    "                    connections.discard(tuple(sorted((node, neighbor))))\n",
    "                min_back_depth = min(min_back_depth, back_depth)\n",
    "            return min_back_depth\n",
    "        dfs(0, 0)\n",
    "        return list(connections)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        adj = collections.defaultdict(list)\n",
    "        ret = set()\n",
    "        for u, v in connections:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "            ret.add((u, v))\n",
    "            \n",
    "        rank = [-inf for _ in range(n)]\n",
    "\n",
    "        \n",
    "        def dfs(pos, depth) -> int:\n",
    "            if rank[pos] >= 0:\n",
    "                return rank[pos]\n",
    "            rank[pos] = depth\n",
    "            min_ret = n\n",
    "            for neighbor in adj[pos]:\n",
    "                # node[pos] is from node[neighbor] at the upper dfs\n",
    "                if rank[neighbor] == rank[pos] - 1:\n",
    "                    continue\n",
    "                neighbor_depth = dfs(neighbor, depth + 1)\n",
    "                if neighbor_depth <= depth:\n",
    "                    ret.discard((pos, neighbor))\n",
    "                    ret.discard((neighbor, pos))\n",
    "                min_ret = min(min_ret, neighbor_depth)\n",
    "            return min_ret\n",
    "\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        \n",
    "        return [list(x) for x in ret]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def num_connected(g):\n",
    "            visited = [False] * n \n",
    "            cc = 0\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    cc += 1\n",
    "                    s = [i]\n",
    "                    while s:\n",
    "                        x = s.pop()\n",
    "                        visited[x] = True\n",
    "                        for y in g[x]:\n",
    "                            if not visited[y]:\n",
    "                                s.append(y)\n",
    "            return cc\n",
    "        def build_graph(conns):\n",
    "            g = collections.defaultdict(list)\n",
    "            for c in conns:\n",
    "                g[c[0]].append(c[1])\n",
    "                g[c[1]].append(c[0])\n",
    "            return g\n",
    "        # res = []\n",
    "        # for i in range(len(connections)):\n",
    "        #     g = build_graph(connections[:i] + connections[i+1:])\n",
    "        #     numc = num_connected(g)\n",
    "        #     print(numc)\n",
    "        #     if numc>1:\n",
    "\n",
    "        #         res.append(connections[i])\n",
    "        # return res\n",
    "        visited = [False] * n\n",
    "        res = []\n",
    "        g = build_graph(connections)\n",
    "        connections = set([tuple(sorted(e)) for e in connections])\n",
    "        # depth = [-1] * (n+1)\n",
    "        # def dfs(x,parent): # return the minimun depth the sub-graph can reach\n",
    "        #     min_depth = n + 1\n",
    "        #     depth[x] = depth[parent] + 1\n",
    "\n",
    "        #     for y in g[x]:\n",
    "        #         if y == parent:\n",
    "        #             continue\n",
    "        #         if depth[y] != -1 and depth[y] < depth[x]:\n",
    "        #             return depth[y]\n",
    "        #         back_depth = dfs(y,x)\n",
    "        #         if back_depth > depth[x]:\n",
    "        #             res.append([x,y])\n",
    "        #         min_depth = min(back_depth, min_depth)\n",
    "            \n",
    "        #     return min_depth\n",
    "        # dfs(0,-1)\n",
    "        rank = [-1] * n # store the depths of nodes in the current dfs\n",
    "        def dfs(x,parent,depth):\n",
    "            if rank[x] > 0:\n",
    "                return rank[x]\n",
    "            min_depth = n+1\n",
    "            rank[x] = depth + 1\n",
    "            for y in g[x]:\n",
    "                if parent == y:\n",
    "                    continue\n",
    "                back_depth = dfs(y,x,depth + 1)\n",
    "                min_depth = min(min_depth, back_depth)\n",
    "                if back_depth <= depth + 1:\n",
    "                    connections.discard(tuple(sorted([x,y])))\n",
    "            return min_depth\n",
    "        dfs(0,-1,0)\n",
    "        return list(connections)\n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def num_connected(g):\n",
    "            visited = [False] * n \n",
    "            cc = 0\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    cc += 1\n",
    "                    s = [i]\n",
    "                    while s:\n",
    "                        x = s.pop()\n",
    "                        visited[x] = True\n",
    "                        for y in g[x]:\n",
    "                            if not visited[y]:\n",
    "                                s.append(y)\n",
    "            return cc\n",
    "        def build_graph(conns):\n",
    "            g = collections.defaultdict(list)\n",
    "            for c in conns:\n",
    "                g[c[0]].append(c[1])\n",
    "                g[c[1]].append(c[0])\n",
    "            return g\n",
    "        # res = []\n",
    "        # for i in range(len(connections)):\n",
    "        #     g = build_graph(connections[:i] + connections[i+1:])\n",
    "        #     numc = num_connected(g)\n",
    "        #     print(numc)\n",
    "        #     if numc>1:\n",
    "\n",
    "        #         res.append(connections[i])\n",
    "        # return res\n",
    "        visited = [False] * n\n",
    "        res = []\n",
    "        g = build_graph(connections)\n",
    "        connections = set([tuple(sorted(e)) for e in connections])\n",
    "        # depth = [-1] * (n+1)\n",
    "        # def dfs(x,parent): # return the minimun depth the sub-graph can reach\n",
    "        #     min_depth = n + 1\n",
    "        #     depth[x] = depth[parent] + 1\n",
    "\n",
    "        #     for y in g[x]:\n",
    "        #         if y == parent:\n",
    "        #             continue\n",
    "        #         if depth[y] != -1 and depth[y] < depth[x]:\n",
    "        #             return depth[y]\n",
    "        #         back_depth = dfs(y,x)\n",
    "        #         if back_depth > depth[x]:\n",
    "        #             res.append([x,y])\n",
    "        #         min_depth = min(back_depth, min_depth)\n",
    "            \n",
    "        #     return min_depth\n",
    "        # dfs(0,-1)\n",
    "        rank = [-1] * n # store the depths of nodes in the current dfs\n",
    "        def dfs(x,parent,depth):\n",
    "            if rank[x] > 0:\n",
    "                return rank[x]\n",
    "            min_depth = n+1\n",
    "            rank[x] = depth + 1\n",
    "            for y in g[x]:\n",
    "                if parent == y:\n",
    "                    continue\n",
    "                back_depth = dfs(y,x,depth + 1)\n",
    "                min_depth = min(min_depth, back_depth)\n",
    "                if back_depth <= depth + 1:\n",
    "                    connections.discard(tuple(sorted([x,y])))\n",
    "            return min_depth\n",
    "        dfs(0,-1,0)\n",
    "        return list(connections)\n",
    "            \n",
    "\n",
    "                \n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = self.create_graph(connections)\n",
    "        node_id_list = [-1] * n\n",
    "        self.res = []\n",
    "        self.dfs(-1, 0, 0, node_id_list, graph)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def create_graph(self, connections):\n",
    "        graph = defaultdict(set)\n",
    "        for node_a, node_b in connections:\n",
    "            graph[node_a].add(node_b)\n",
    "            graph[node_b].add(node_a)\n",
    "        return graph\n",
    "\n",
    "    def dfs(self, parent, node, node_id, node_id_list, graph):\n",
    "        node_id_list[node] = node_id\n",
    "        for neighbor in graph[node]:\n",
    "            if neighbor == parent:\n",
    "                continue\n",
    "            # 未访问过, 计算 neigbor id\n",
    "            if node_id_list[neighbor] == -1:\n",
    "                node_id_list[node] = min(node_id_list[node], self.dfs(node, neighbor, node_id + 1, node_id_list, graph))\n",
    "            # 访问过, 直接使用 neigbor id\n",
    "            else:\n",
    "                node_id_list[node] = min(node_id_list[node],node_id_list[neighbor])\n",
    "        # 与父节点给的id相同，且不是 root\n",
    "        if node_id_list[node] == node_id and node != 0:\n",
    "            self.res.append([parent,node])\n",
    "\n",
    "        return node_id_list[node]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        m = defaultdict(list)\n",
    "        for a,b in connections:\n",
    "            m[a].append(b)\n",
    "            m[b].append(a)\n",
    "        dfs, low = [-1] * n, [-1] * n\n",
    "        time = 0\n",
    "        def Tarjan(node,father):\n",
    "            nonlocal time\n",
    "            time += 1\n",
    "            dfs[node] = low[node] = time\n",
    "            for k in m[node]:\n",
    "                if dfs[k] == -1:\n",
    "                    Tarjan(k,node)\n",
    "                    low[node] = min(low[node],low[k])\n",
    "                elif k != father:\n",
    "                    low[node] = min(low[node], dfs[k])\n",
    "        Tarjan(0,-1)\n",
    "        res = []\n",
    "        visited = [0] * n\n",
    "        def fun(node):\n",
    "            if visited[node] == 1:\n",
    "                return\n",
    "            visited[node]=1\n",
    "            for k in m[node]:\n",
    "                if dfs[node] < low[k]:\n",
    "                    res.append([node,k])\n",
    "                fun(k)\n",
    "        fun(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        adj = collections.defaultdict(list)\n",
    "        for a, b in connections: \n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a) \n",
    "\n",
    "        low = {} \n",
    "        rank = {} \n",
    "    \n",
    "        def dfs(node, index): \n",
    "            low[node] = index\n",
    "            rank[node] = index \n",
    "            for nei in adj[node]:\n",
    "                if nei not in rank:\n",
    "                    # unvisited\n",
    "                    dfs(nei, index+1)\n",
    "                if rank[nei] != rank[node] - 1 and low[nei] < low[node]: \n",
    "                    low[node] = low[nei] \n",
    "        \n",
    "        dfs(0, 0) \n",
    "\n",
    "        res = []\n",
    "        for a, b in connections:\n",
    "            if low[a] > rank[b] or low[b] > rank[a]: \n",
    "                res.append([a, b])\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph: list[list[int]] = [[] for _ in range(n)]\n",
    "        for index, (i, j) in enumerate(connections):\n",
    "            graph[i].append([j, index])\n",
    "            graph[j].append([i, index])\n",
    "        m = len(connections)\n",
    "        visitedNode = [0]*n\n",
    "        visitedEdge = [0]*(m+1)\n",
    "        circle = [0]*(m+1)\n",
    "        ls: list[int] = [[0, m]]\n",
    "        def dfs(node: int, edge: int):\n",
    "            if visitedEdge[edge]:\n",
    "                return\n",
    "            visitedEdge[edge] = 1\n",
    "            if visitedNode[node]:\n",
    "                circle[edge] = 1\n",
    "                for i in range(len(ls)-1, -1, -1):\n",
    "                    _node, _edge = ls[i]\n",
    "                    if _node == node or circle[_edge]:\n",
    "                        break\n",
    "                    ls.pop()\n",
    "                    circle[_edge] = 1\n",
    "                return\n",
    "            visitedNode[node] = 1\n",
    "            ls.append([node, edge])\n",
    "            for j in graph[node]:\n",
    "                dfs(*j)\n",
    "            if ls and ls[-1] == [node, edge]:\n",
    "                ls.pop()\n",
    "            return\n",
    "        dfs(0, m)\n",
    "        return [connections[i] for i in range(m) if circle[i] == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        path = [[] for i in range(n)]\n",
    "        for x, y in connections:\n",
    "            path[x].append(y)\n",
    "            path[y].append(x)\n",
    "        order = []\n",
    "        def dfs(node, lastnode, order):\n",
    "            visit[node] = 1\n",
    "            toremove = []\n",
    "            for nextNode in path[node]:\n",
    "                if nextNode!=lastnode and visit[nextNode]==0:\n",
    "                    dfs(nextNode, node, order)\n",
    "                    toremove.append(nextNode)\n",
    "            for x in toremove:\n",
    "                path[node].remove(x)\n",
    "            visit[node] = 2\n",
    "            order.append(node)\n",
    "        ans = []\n",
    "        visit = [0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            if visit[i]==0:\n",
    "                dfs(i, -1, order)\n",
    "        visit = [0 for i in range(n)]\n",
    "        components = []\n",
    "        order.reverse()\n",
    "        for i in order:\n",
    "            if visit[i]==0:\n",
    "                tmp = []\n",
    "                dfs(i, -1, tmp)\n",
    "                components.append(tmp)\n",
    "        print(components)\n",
    "        componentsId = [-1 for i in range(n)]\n",
    "        for i in range(len(components)):\n",
    "            for x in  components[i]:\n",
    "                componentsId[x] = i\n",
    "        for x,y in connections:\n",
    "            if componentsId[x]!=componentsId[y]:\n",
    "                ans.append([x,y])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        #解题思路 https://www.bilibili.com/video/BV15t4y197eq/\n",
    "        #相当于把non-critical connection看作一个环(cycle)，cycle上的node拥有相同id\n",
    "        #连接不同id的edge就是critical connection\n",
    "        #但判断是否critical并加入res需要看自己的id是否有被update(因为有可能一个node同时在两个环上)\n",
    "        graph = {}\n",
    "        for [u, v] in connections:\n",
    "            if u not in graph.keys(): graph[u] = set([v])\n",
    "            else: graph[u].add(v)\n",
    "            if v not in graph.keys(): graph[v] = set([u])\n",
    "            else: graph[v].add(u)\n",
    "        res =[]\n",
    "        ids = [-1 for _ in range(n)]\n",
    "\n",
    "        def dfs(cur, parent, curId):\n",
    "            ids[cur]=curId\n",
    "            for v in graph[cur]:\n",
    "                if v == parent: continue # 忽略自己\n",
    "                elif ids[v] == -1:\n",
    "                    ids[cur] = min(ids[cur], dfs(v, cur, curId+1))\n",
    "                else:\n",
    "                    ids[cur] = min(ids[cur], ids[v])\n",
    "\n",
    "            # 整理完的最终id == cur_id（上面传进来的）\n",
    "            # 是环的脑袋\n",
    "            # 另外不要忘记 排除特殊\n",
    "            if ids[cur]==curId and cur!=0:\n",
    "                #注意这里是加[cur, parent]这个edge\n",
    "                res.append((cur,parent))\n",
    "            return ids[cur]\n",
    "\n",
    "        #注意这里root的parent要设置成-1\n",
    "        dfs(0, -1, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    T = 0\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in connections:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "\n",
    "        self.T = 0\n",
    "\n",
    "        result, stack, dfn, low = [], [], {}, {}\n",
    "        def dfs(a: int, parent: int):\n",
    "            self.T += 1\n",
    "            stack.append(a)\n",
    "            dfn[a] = low[a] = self.T\n",
    "            for b in graph[a]:\n",
    "                if b == parent:\n",
    "                    continue\n",
    "                if not dfn.get(b):\n",
    "                    dfs(b, a)\n",
    "                    low[a] = min(low[a], low[b])\n",
    "                else:\n",
    "                    low[a] = min(low[a], low[b])\n",
    "            if parent != -1 and low[a] > dfn[parent]:\n",
    "                result.append([a, parent])\n",
    "        dfs(0, -1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        ind = [0] * n\n",
    "        g = defaultdict(list)\n",
    "        for a, b in connections:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            ind[a] += 1\n",
    "            ind[b] += 1\n",
    "\n",
    "        def tarjan(edges):\n",
    "            vis = [0] * n\n",
    "            root = [0] * n\n",
    "            index = 1\n",
    "            v = set()\n",
    "            res = []\n",
    "            def dfs(node, fa):\n",
    "                nonlocal index\n",
    "                vis[node] = root[node] = index\n",
    "                index += 1\n",
    "                v.add(node)\n",
    "                for b in g[node]:\n",
    "                    if b != fa:\n",
    "                        if not vis[b]:\n",
    "                            dfs(b, node)\n",
    "                            root[node] = min(root[node], root[b])\n",
    "                            if vis[node] < root[b]:\n",
    "                                res.append([b, node])\n",
    "                        else:\n",
    "                            root[node] = min(root[node], vis[b])\n",
    "            dfs(0, -1)\n",
    "            return res\n",
    "        return tarjan(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = { i : [] for i in range(n)}\n",
    "        for conn in connections:\n",
    "            graph[conn[0]].append(conn[1])\n",
    "            graph[conn[1]].append(conn[0])\n",
    "\n",
    "        # 集合，注意排序让小的节点在前面，避免重复\n",
    "        connections = set(map(tuple, (map(sorted, connections))))\n",
    "        # DFS 访问每个节点的深度，只有访问过的路径有深度，初始化为 -1\n",
    "        rank = [-1] * n\n",
    "\n",
    "        def dfs(node, parent, depth):\n",
    "            # 如果已经访问过该边，则已经记录了 rank\n",
    "            if rank[node] >= 0:\n",
    "                return rank[node]\n",
    "            # 记录当前的 rank，默认会回溯 +1\n",
    "            rank[node] = depth\n",
    "            # 最大可能为 n\n",
    "            min_depth = n\n",
    "            for v in graph[node]:\n",
    "                # 跳过父节点\n",
    "                if v == parent:\n",
    "                    continue\n",
    "                # 获得子节点的最小深度\n",
    "                back_depth = dfs(v, node, depth+1)\n",
    "                # 子节点比当前深度小，显然是环\n",
    "                if back_depth <= depth:\n",
    "                    connections.discard(tuple(sorted((node, v))))\n",
    "                # 当前节点的最小深度也要记录下来，以便把整个环去掉\n",
    "                min_depth = min(min_depth, back_depth)\n",
    "            # 返回给父节点\n",
    "            return min_depth\n",
    "        dfs(0, -1, 0)\n",
    "        return list(connections)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        graph= defaultdict(list)\n",
    "        for u , v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        t = defaultdict(int)\n",
    "\n",
    "        def targan(node,parent,step):\n",
    "            t[node] = step\n",
    "            d[node] = step\n",
    "\n",
    "            for nxt in graph[node]:\n",
    "                if t[nxt] == 0:\n",
    "                    targan(nxt,node,step+1)\n",
    "                    d[node] = min(d[node],d[nxt])\n",
    "                    if t[node] < d[nxt]:\n",
    "                        ans.append([node,nxt])\n",
    "                elif nxt != parent:\n",
    "                    d[node] = min(d[node],d[nxt])\n",
    "        \n",
    "        ans = []\n",
    "        targan(0,-1,1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def check_graph(edge: List[list], n):\n",
    "            # edge为边连接关系，n为节点数\n",
    "\n",
    "            # 访问序号与根节点序号\n",
    "            visit = [0] * n\n",
    "            root = [0] * n\n",
    "            # 割点\n",
    "            cut_node = []\n",
    "            # 割边\n",
    "            cut_edge = []\n",
    "            # 强连通分量子树\n",
    "            sub_group = []\n",
    "\n",
    "            # 中间变量\n",
    "            stack = []\n",
    "            index = 1\n",
    "\n",
    "            def tarjan(i, father):\n",
    "                nonlocal index\n",
    "                visit[i] = root[i] = index\n",
    "                index += 1\n",
    "                stack.append(i)\n",
    "                for j in edge[i]:\n",
    "                    if j != father:\n",
    "                        if not visit[j]:\n",
    "                            tarjan(j, i)\n",
    "                            root[i] = min(root[i], root[j])\n",
    "                            if visit[i] < root[j]:\n",
    "                                cut_edge.append([i, j])\n",
    "                            if visit[i] <= root[j]:\n",
    "                                cut_node.append(i)\n",
    "                        elif j in stack:\n",
    "                            root[i] = min(root[i], visit[j])\n",
    "\n",
    "                if root[i] == visit[i]:\n",
    "                    lst = []\n",
    "                    while stack[-1] != i:\n",
    "                        lst.append(stack.pop())\n",
    "                    lst.append(stack.pop())\n",
    "                    r = min(root[ls] for ls in lst)\n",
    "                    for ls in lst:\n",
    "                        root[ls] = r\n",
    "                    sub_group.append(lst)\n",
    "                return\n",
    "\n",
    "            for k in range(n):\n",
    "                if not visit[k]:\n",
    "                    tarjan(k, -1)\n",
    "            return cut_edge, cut_node, sub_group\n",
    "\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            edges[a].append(b)\n",
    "            edges[b].append(a)\n",
    "        cut_edge, cut_node, sub_group = check_graph(edges, n)\n",
    "        return cut_edge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    visited, ord, low, cnt, res, graph = [], [], [], 0, [], []\n",
    "\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        self.graph = [0] * n\n",
    "        for i in range(n):\n",
    "            self.graph[i] = set()\n",
    "            \n",
    "        for v1, v2 in connections:\n",
    "            self.graph[v1].add(v2)\n",
    "            self.graph[v2].add(v1)\n",
    "\n",
    "        self.visited = [False] * n\n",
    "        self.ord = [0] * n\n",
    "        self.low = [0] * n\n",
    "        self.res = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if not self.visited[i]:\n",
    "                self.dfs(i, i)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, v, parent):\n",
    "        self.visited[v] = True\n",
    "        self.ord[v] = self.cnt\n",
    "        self.low[v] = self.cnt\n",
    "        self.cnt += 1\n",
    "\n",
    "        for w in self.graph[v]:\n",
    "            if not self.visited[w]:\n",
    "                self.dfs(w, v)\n",
    "                self.low[v] = min(self.low[v], self.low[w])\n",
    "\n",
    "                if self.low[w] > self.ord[v]:\n",
    "                    self.res.append([v, w])\n",
    "            elif w != parent:\n",
    "                self.low[v] = min(self.low[v], self.low[w])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        if n == 2:#如果只有两点，两点一线必然是关键边\n",
    "            return connections\n",
    "        def dfs(x):#深搜，寻找两点之间是否相通\n",
    "            if x == j:#如果到达终点\n",
    "                return True\n",
    "            for y in d.get(x, []):\n",
    "                if degree[y] > 1 and (x, y) != (i, j) and visit[y] == 0:#不需要走链，且不能起点和终点直连且下个点未到达过\n",
    "                    visit[y] = 1\n",
    "                    if dfs(y):\n",
    "                        return True\n",
    "            return False\n",
    "        res = []\n",
    "        degree = [0 for i in range(n)]#边数\n",
    "        d = {}#每个点能到达的其他点列表\n",
    "        for i, j in connections:\n",
    "            if i not in d:\n",
    "                d[i] = set()\n",
    "            if j not in d:\n",
    "                d[j] = set()\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "            degree[i] += 1#边+1\n",
    "            degree[j] += 1#边+1\n",
    "        deq = collections.deque()#bfs队列\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:#如果为1，则是链头\n",
    "                deq.append(i)\n",
    "        while deq:\n",
    "            i = deq.popleft()\n",
    "            for j in d[i]:\n",
    "                if degree[j] > 1:\n",
    "                    res.append([i, j])#加入关键边\n",
    "                    degree[j] -= 1#边数减1\n",
    "                    if degree[j] == 1:#如果链未入环，继续遍历\n",
    "                        deq.append(j)\n",
    "        for i, j in connections:\n",
    "            if (degree[i] == 3 and degree[j] >= 3) or (degree[j] == 3 and degree[i] >= 3):#如果满足上面的两个条件\n",
    "                visit = [0 for i in range(n)]\n",
    "                if not dfs(i):#深搜判断是否为关键边\n",
    "                    res.append([i, j])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        if n == 2:#如果只有两点，两点一线必然是关键边\n",
    "            return connections\n",
    "        def dfs(x):#深搜，寻找两点之间是否相通\n",
    "            if x == j:#如果到达终点\n",
    "                return True\n",
    "            for y in d.get(x, []):\n",
    "                if degree[y] > 1 and (x, y) != (i, j) and visit[y] == 0:#不需要走链，且不能起点和终点直连且下个点未到达过\n",
    "                    visit[y] = 1\n",
    "                    if dfs(y):\n",
    "                        return True\n",
    "            return False\n",
    "        res = []\n",
    "        degree = [0 for i in range(n)]#边数\n",
    "        d = {}#每个点能到达的其他点列表\n",
    "        for i, j in connections:\n",
    "            if i not in d:\n",
    "                d[i] = set()\n",
    "            if j not in d:\n",
    "                d[j] = set()\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "            degree[i] += 1#边+1\n",
    "            degree[j] += 1#边+1\n",
    "        deq = collections.deque()#bfs队列\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:#如果为1，则是链头\n",
    "                deq.append(i)\n",
    "        while deq:\n",
    "            i = deq.popleft()\n",
    "            for j in d[i]:\n",
    "                if degree[j] > 1:\n",
    "                    res.append([i, j])#加入关键边\n",
    "                    degree[j] -= 1#边数减1\n",
    "                    if degree[j] == 1:#如果链未入环，继续遍历\n",
    "                        deq.append(j)\n",
    "        for i, j in connections:\n",
    "            if (degree[i] == 3 and degree[j] >= 3) or (degree[j] == 3 and degree[i] >= 3):#如果满足上面的两个条件\n",
    "                visit = [0 for i in range(n)]\n",
    "                if not dfs(i):#深搜判断是否为关键边\n",
    "                    res.append([i, j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        DEBUG = 1\n",
    "\n",
    "        ## 先构建图\n",
    "        g = defaultdict(set)\n",
    "        for i, j in connections:\n",
    "            g[i].add(j)\n",
    "            g[j].add(i)\n",
    "\n",
    "        if DEBUG:\n",
    "            print(g)\n",
    "        \n",
    "        ## 记录到当前节点的步数\n",
    "        step = [-1] * n\n",
    "\n",
    "        ## 通过一个 DFS 来的到最小步数\n",
    "        def DFS(step, g, res, lev, curr, parent):\n",
    "\n",
    "            if curr == 1:\n",
    "                print(lev)\n",
    "\n",
    "            step[curr] = lev + 1\n",
    "\n",
    "            ## 遍历当前节点的所有孩子\n",
    "            for child in g[curr]:\n",
    "                ## 如果我的子节点也是我的父亲节点, 我们之间一定不是关键连接\n",
    "\n",
    "                if child == parent:\n",
    "                    continue\n",
    "\n",
    "                elif step[child] == -1:\n",
    "                    ## 如果我们之前没有访问过这个子节点\n",
    "                    step[curr] = min(step[curr], DFS(step, g, res, lev + 1, child, curr))\n",
    "                else:\n",
    "                    step[curr] = min(step[curr], step[child])\n",
    "                \n",
    "\n",
    "            if step[curr] == lev + 1 and curr != 0:\n",
    "                res.append([parent, curr])\n",
    "            ## 返回当前节点的 step\n",
    "            return step[curr]\n",
    "                \n",
    "        res = list()\n",
    "        DFS(step, g, res, -1, 0, -1)\n",
    "        if DEBUG:\n",
    "            print(step)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        adj = {}\n",
    "        for x, y in connections:\n",
    "            if x not in adj:\n",
    "                adj[x] = []\n",
    "            adj[x].append(y)\n",
    "            if y not in adj:\n",
    "                adj[y] = []\n",
    "            adj[y].append(x)\n",
    "        current = 0\n",
    "        line = [0]\n",
    "        lineSet = set([0])\n",
    "        reached = set([0])\n",
    "        self.isBridge = set()\n",
    "        self.timestamp = 0\n",
    "        self.dfn, self.low = [-1] * n, [-1] * n\n",
    "        self.dfs(adj, x, 0)\n",
    "        res = []\n",
    "        for x, y in connections:\n",
    "            if (x, y) in self.isBridge or (y, x) in self.isBridge:\n",
    "                res.append([x, y])\n",
    "        return res\n",
    "\n",
    "    def dfs(self, adj, x, father):\n",
    "        self.dfn[x] = self.timestamp\n",
    "        self.low[x] = self.timestamp\n",
    "        self.timestamp += 1\n",
    "        for y in adj[x]:\n",
    "            if self.dfn[y] == -1:\n",
    "                self.dfs(adj, y, x)\n",
    "                self.low[x] = min(self.low[x], self.low[y])\n",
    "                if self.low[y] > self.dfn[x]:\n",
    "                    self.isBridge.add((x, y))\n",
    "            elif self.dfn[y] < self.dfn[x] and y != father:\n",
    "                self.low[x] = min(self.low[x], self.dfn[y])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Tarjan:\n",
    "    '''\n",
    "        n: 顶点数量\n",
    "        edges: 存储的边\n",
    "        root: 以root为根节点\n",
    "    '''\n",
    "    def __init__(self, n: int, edges: List[List[int]],root:int) -> None:\n",
    "        self.low = [0] * (n + 1)    # 最短到达该顶点时间\n",
    "        self.dfn = [0] * (n + 1)    # dfs序到达该顶点时间\n",
    "        self.parent = [-1] * (n + 1)# 顶点的父节点\n",
    "        self.vis = [False] * (n + 1)# 该顶点是否被访问\n",
    "        self.isCutVer = [False] * (n + 1) # 是否是割点\n",
    "        self.isBridge = [False] * (n + 1) # (parent[v], v) 是否是桥\n",
    "        self.clock = 1 # 时间戳\n",
    "\n",
    "        self.V = None    # 存储割点\n",
    "        self.B = None    # 存储桥\n",
    "\n",
    "        # 边存储方式 (u, v)\n",
    "        self.edges = edges\n",
    "        self.n = n\n",
    "        self.g = [[] for _ in range(n + 1)]\n",
    "        for u,v in edges:\n",
    "            self.g[u].append(v)\n",
    "            self.g[v].append(u)\n",
    "        \n",
    "        self.tarjan(root, -1)\n",
    "\n",
    "    def tarjan(self,u:int, father:int):\n",
    "        self.parent[u] = father\n",
    "        self.vis[u] = True\n",
    "        self.low[u] = self.dfn[u] = self.clock\n",
    "        self.clock += 1\n",
    "        child = 0\n",
    "        for v in self.g[u]:\n",
    "            if not self.vis[v]:\n",
    "                child += 1\n",
    "                self.tarjan(v, u)\n",
    "                self.low[u] = min(self.low[u], self.low[v])\n",
    "                # 如果存在子节点 low[v] >= dfn[u] 则说明子节点v必经过u, u是个割点\n",
    "                if father != u and self.low[v] >= self.dfn[u] and not self.isCutVer[u]:\n",
    "                    self.isCutVer[u] = True\n",
    "                # 如果子节点 low[v] > dfn[u] 则说明子节点v必经过u, (u, v) 是个桥\n",
    "                if self.low[v] > self.dfn[u]:\n",
    "                    self.isBridge[v] = True\n",
    "            elif v != father:\n",
    "                self.low[u] = min(self.low[u], self.low[v])\n",
    "        # 超过一个孩子则该点是割点\n",
    "        if father == u and child >= 2 and not self.isCutVer[u]:\n",
    "            self.isCutVer[u] = True\n",
    "\n",
    "    def getCutVer(self) -> Set:\n",
    "        self.V = set()\n",
    "        for i, x in enumerate(self.isCutVer):\n",
    "            if x:\n",
    "                self.V.add(i)\n",
    "        return self.V\n",
    "    \n",
    "    def getBridge(self) -> Set:\n",
    "        self.B = set()\n",
    "        for i in range(self.n + 1):\n",
    "            if self.isBridge[i]:\n",
    "                self.B.add((i, self.parent[i]))\n",
    "        return self.B\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        tar = Tarjan(n, connections, 0)\n",
    "        s  = tar.getBridge()\n",
    "        ans = []\n",
    "        for u,v in connections:\n",
    "            if (u,v) in s or (v,u) in s:\n",
    "                ans.append([u,v])\n",
    "        return ans\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        g = defaultdict(set)\n",
    "        for a, b in connections:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "\n",
    "        times = [-1] * n\n",
    "        rs = []\n",
    "\n",
    "        # 返回所有间接连通节点的最小可达时间\n",
    "        def dfs(cur, fa, g, now) -> int:\n",
    "            if times[cur] != -1:\n",
    "                return times[cur]\n",
    "\n",
    "            times[cur] = now\n",
    "            for next in g[cur]:\n",
    "                if next == fa:\n",
    "                    continue\n",
    "\n",
    "                minTime = dfs(next, cur, g, now+1)\n",
    "                times[cur] = min(times[cur], minTime)\n",
    "\n",
    "            # 如有有环，则必然 times[cur] < now\n",
    "            # 环中的边必然不是关键连接\n",
    "            if times[cur] == now and fa != -1:\n",
    "                rs.append([fa, cur])\n",
    "\n",
    "            return times[cur]\n",
    "\n",
    "        dfs(0, -1, g, 0)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Tarjan:\n",
    "    '''\n",
    "        n: 顶点数量\n",
    "        edges: 存储的边\n",
    "        root: 以root为根节点\n",
    "    '''\n",
    "    def __init__(self, n: int, edges: List[List[int]],root:int) -> None:\n",
    "        self.low = [0] * (n + 1)    # 最短到达该顶点时间\n",
    "        self.dfn = [0] * (n + 1)    # dfs序到达该顶点时间\n",
    "        self.parent = [-1] * (n + 1)# 顶点的父节点\n",
    "        self.vis = [False] * (n + 1)# 该顶点是否被访问\n",
    "        self.isCutVer = [False] * (n + 1) # 是否是割点\n",
    "        self.isBridge = [False] * (n + 1) # (parent[v], v) 是否是桥\n",
    "        self.clock = 1 # 时间戳\n",
    "        self.V = []    # 存储割点\n",
    "        self.E = []    # 存储桥\n",
    "        # 边存储方式 (u, v)\n",
    "        self.edges = edges\n",
    "        self.n = n\n",
    "        self.g = [[] for _ in range(n + 1)]\n",
    "        for u,v in edges:\n",
    "            self.g[u].append(v)\n",
    "            self.g[v].append(u)\n",
    "        \n",
    "        self.tarjan(root, -1)\n",
    "\n",
    "    def tarjan(self,u:int, father:int):\n",
    "        self.parent[u] = father\n",
    "        self.vis[u] = True\n",
    "        self.low[u] = self.dfn[u] = self.clock\n",
    "        self.clock += 1\n",
    "        child = 0\n",
    "        for v in self.g[u]:\n",
    "            if not self.vis[v]:\n",
    "                child += 1\n",
    "                self.tarjan(v, u)\n",
    "                self.low[u] = min(self.low[u], self.low[v])\n",
    "                # 如果存在子节点 low[v] >= dfn[u] 则说明子节点v必经过u, u是个割点\n",
    "                if father != u and self.low[v] >= self.dfn[u] and not self.isCutVer[u]:\n",
    "                    self.isCutVer[u] = True\n",
    "                # 如果子节点 low[v] > dfn[u] 则说明子节点v必经过u, (u, v) 是个桥\n",
    "                if self.low[v] > self.dfn[u]:\n",
    "                    self.isBridge[v] = True\n",
    "            elif v != father:\n",
    "                self.low[u] = min(self.low[u], self.low[v])\n",
    "        # 超过一个孩子则该点是割点\n",
    "        if father == u and child >= 2 and not self.isCutVer[u]:\n",
    "            self.isCutVer[u] = True\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        tar = Tarjan(n, connections, 0)\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            if tar.isBridge[i]:\n",
    "                s.add((i, tar.parent[i]))\n",
    "        ans = []\n",
    "        for u,v in connections:\n",
    "            if (u,v) in s or (v,u) in s:\n",
    "                ans.append([u,v])\n",
    "        return ans\n",
    "\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        dfn = [-1]*n\n",
    "        low = [-1]*n\n",
    "        timeS = 0\n",
    "        res = []\n",
    "        edges = collections.defaultdict(set)\n",
    "        for con in connections:\n",
    "            edges[con[0]].add(con[1])\n",
    "            edges[con[1]].add(con[0])\n",
    "        def tarjan(i,parent):\n",
    "            nonlocal timeS\n",
    "            dfn[i] = timeS\n",
    "            low[i] = timeS\n",
    "            timeS+=1\n",
    "            for node in edges[i]:\n",
    "                if dfn[node]==-1:\n",
    "                    tarjan(node,i)\n",
    "                    low[i] = min(low[i],low[node])\n",
    "                elif node!=parent:\n",
    "                    low[i] = min(low[i],low[node])\n",
    "            if dfn[i]==low[i] and i!=parent:\n",
    "                res.append([parent,i])\n",
    "        tarjan(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = {i:set() for i in range(n)}\n",
    "        id_array = [-1 for _ in range(n)]\n",
    "        for begin, end in connections:\n",
    "            graph[begin].add(end)\n",
    "            graph[end].add(begin)\n",
    "        \n",
    "        result = []\n",
    "        def dfs(node, node_id, parent):\n",
    "            id_array[node] = node_id\n",
    "\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor == parent:\n",
    "                    continue\n",
    "                elif id_array[neighbor] == -1:\n",
    "                    id_array[node] = min(id_array[node], dfs(neighbor, node_id + 1, node))\n",
    "                else:\n",
    "                    id_array[node] = min(id_array[node], id_array[neighbor])\n",
    "            if id_array[node] == node_id and node != 0:\n",
    "                result.append([parent, node])\n",
    "            return id_array[node]\n",
    "        dfs(0, 0, -1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        adjvex = defaultdict(set)\n",
    "        for x, y in connections:\n",
    "            adjvex[x].add(y)\n",
    "            adjvex[y].add(x)\n",
    "        \n",
    "\n",
    "        dfn = [-1 for _ in range(n)]    #dfs访问中的实际时间\n",
    "        low = [-1 for _ in range(n)]    #dfs中通过无向边可以向前回溯到的最早的时间点\n",
    "        self.T = 0\n",
    "\n",
    "        def tarjan(x: int, parent: int) -> None:\n",
    "            dfn[x] = self.T\n",
    "            low[x] = self.T\n",
    "            self.T += 1\n",
    "            for y in adjvex[x]:\n",
    "                if y == parent:                 #可能是父节点\n",
    "                    continue\n",
    "                if dfn[y] == -1:                #还没访问过\n",
    "                    tarjan(y, x)                #先访问y，访问了才能计算\n",
    "                    low[x] = min(low[x], low[y])\n",
    "                    if low[y] > dfn[x]:         #x 和 y不在一个强连通分量\n",
    "                        res.append([x, y])\n",
    "                elif dfn[y] != -1:              #访问过了\n",
    "                    low[x] = min(low[x], dfn[y])\n",
    "        res = []\n",
    "        tarjan(0, -1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "class Solution:\r\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\r\n",
    "        res = []\r\n",
    "        graph = [defaultdict(bool) for _ in range(n)]\r\n",
    "        for edge in connections:\r\n",
    "            graph[edge[0]][edge[1]] = True\r\n",
    "            graph[edge[1]][edge[0]] = True\r\n",
    "        low = [-1] * n\r\n",
    "        def Tarjan(prev, cur, index):\r\n",
    "            low[cur] = index\r\n",
    "            dfn = low[cur]\r\n",
    "            for nxt in graph[cur]:\r\n",
    "                if nxt == prev:\r\n",
    "                    continue\r\n",
    "                if low[nxt] == -1:\r\n",
    "                    index += 1\r\n",
    "                    Tarjan(cur, nxt, index)\r\n",
    "                if low[nxt] > dfn:\r\n",
    "                    res.append([cur, nxt])\r\n",
    "                low[cur] = min(low[cur], low[nxt])\r\n",
    "        Tarjan(0, 0, 0)\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "'''\n",
    "Trajan算法求无向图的桥\n",
    "'''\n",
    "\n",
    "\n",
    "def getCuttingPointAndCuttingEdge(edges: [[]]):\n",
    "    link, dfn, low = {}, {}, {}  # link为字典邻接表\n",
    "    global_time = [0]\n",
    "    for a, b in edges:\n",
    "        if a not in link:\n",
    "            link[a] = []\n",
    "        if b not in link:\n",
    "            link[b] = []\n",
    "        link[a].append(b)  # 无向图\n",
    "        link[b].append(a)  # 无向图\n",
    "        dfn[a], dfn[b] = 0x7fffffff, 0x7fffffff\n",
    "        low[a], low[b] = 0x7fffffff, 0x7fffffff\n",
    "\n",
    "    cutting_points, cutting_edges = [], []\n",
    "\n",
    "    def dfs(cur, prev, root):\n",
    "        global_time[0] += 1\n",
    "        dfn[cur], low[cur] = global_time[0], global_time[0]\n",
    "\n",
    "        children_cnt = 0\n",
    "        flag = False\n",
    "        for next in link[cur]:\n",
    "            if next != prev:\n",
    "                if dfn[next] == 0x7fffffff:\n",
    "                    children_cnt += 1\n",
    "                    dfs(next, cur, root)\n",
    "\n",
    "                    if cur != root and low[next] >= dfn[cur]:\n",
    "                        flag = True\n",
    "                    low[cur] = min(low[cur], low[next])\n",
    "\n",
    "                    if low[next] > dfn[cur]:\n",
    "                        cutting_edges.append([cur, next] if cur < next else [next, cur])\n",
    "                else:\n",
    "                    low[cur] = min(low[cur], dfn[next])\n",
    "\n",
    "        if flag or (cur == root and children_cnt >= 2):\n",
    "            cutting_points.append(cur)\n",
    "\n",
    "    dfs(edges[0][0], None, edges[0][0])\n",
    "    return cutting_points, cutting_edges\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: [[int]]) -> [[int]]:\n",
    "\n",
    "        cutting_dots, cutting_edges = getCuttingPointAndCuttingEdge(connections)\n",
    "        return [[a, b] for a, b in cutting_edges]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple \n",
    "'''\n",
    "Trajan算法求无向图的桥\n",
    "'''\n",
    "class Tarjan:\n",
    "    # 求无向连通图的桥\n",
    "    @staticmethod\n",
    "    def getCuttingPointAndCuttingEdge(edges: List[Tuple]):\n",
    "        link, dfn, low = {}, {}, {} # link 为字典邻接表\n",
    "        global_time = [0]\n",
    "        for a, b in edges:\n",
    "            if a not in link:\n",
    "                link[a] = []\n",
    "            if b not in link:\n",
    "                link[b] = []\n",
    "            link[a].append(b) # 无向图\n",
    "            link[b].append(a) # 无向图\n",
    "            dfn[a], dfn[b] = 0x7fffffff, 0x7fffffff\n",
    "            low[a], low[b] = 0x7fffffff, 0x7fffffff\n",
    " \n",
    " \n",
    "        cutting_points, cutting_edges = [], []\n",
    " \n",
    "        def dfs(cur, prev, root):\n",
    "            global_time[0] += 1\n",
    "            dfn[cur], low[cur] = global_time[0], global_time[0]\n",
    " \n",
    "            children_cnt = 0\n",
    "            flag = False\n",
    "            for next in link[cur]:\n",
    "                if next != prev:\n",
    "                    if dfn[next] == 0x7fffffff:\n",
    "                        children_cnt += 1\n",
    "                        dfs(next, cur, root)\n",
    " \n",
    "                        if cur != root and low[next] >= dfn[cur]:\n",
    "                            flag = True\n",
    "                        low[cur] = min(low[cur], low[next])\n",
    " \n",
    "                        if low[next] > dfn[cur]:\n",
    "                            cutting_edges.append([cur, next] if cur < next else [next, cur])\n",
    "                    else:\n",
    "                        low[cur] = min(low[cur], dfn[next])\n",
    " \n",
    "            if flag or (cur == root and children_cnt >= 2):\n",
    "                cutting_points.append(cur)\n",
    " \n",
    "        dfs(edges[0][0], None, edges[0][0])\n",
    "        return cutting_points, cutting_edges\n",
    " \n",
    " \n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        edges = [(a, b) for a, b in connections]\n",
    "        cutting_dots, cutting_edges = Tarjan.getCuttingPointAndCuttingEdge(connections)\n",
    "        #edges)\n",
    "        return [[a, b] for a, b in cutting_edges]\n",
    " \n",
    " \n",
    "connections = [[0,1],[1,2],[2,0],[1,3]]\n",
    "n = 4\n",
    "s = Solution()\n",
    "result = s.criticalConnections(n,connections)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import DefaultDict, List, Set, Tuple\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        g = defaultdict(set)\n",
    "        for a,b in connections:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        tarjan = Tarjan()\n",
    "        node,edge = tarjan.getCuttingPointAndCuttingEdge(n,g)\n",
    "        return edge\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Tarjan:\n",
    "    INF = int(1e20)\n",
    "\n",
    "    @staticmethod\n",
    "    def getSCC(\n",
    "        n: int, adjMap: DefaultDict[int, Set[Tuple[int, int]]]\n",
    "    ) -> Tuple[int, List[List[int]], List[int]]:\n",
    "        \"\"\"Tarjan求解有向图的强连通分量\n",
    "\n",
    "        Args:\n",
    "            n (int): 结点0-n-1\n",
    "            adjMap (DefaultDict[int, Set[int]]): 图\n",
    "\n",
    "        Returns:\n",
    "            Tuple[int, List[List[int]], List[int]]: SCC的数量、分组、每个结点对应的SCC编号\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(cur: int) -> None:\n",
    "            if visited[cur]:\n",
    "                return\n",
    "            visited[cur] = True\n",
    "\n",
    "            nonlocal dfsId, SCCId\n",
    "            order[cur] = low[cur] = dfsId\n",
    "            dfsId += 1\n",
    "            stack.append(cur)\n",
    "            inStack[cur] = True\n",
    "\n",
    "            for next, _ in adjMap[cur]:\n",
    "                if not visited[next]:\n",
    "                    dfs(next)\n",
    "                    low[cur] = min(low[cur], low[next])\n",
    "                elif inStack[next]:\n",
    "                    low[cur] = min(low[cur], low[next])\n",
    "            if order[cur] == low[cur]:\n",
    "                while stack:\n",
    "                    top = stack.pop()\n",
    "                    inStack[top] = False\n",
    "                    SCCGroupById[SCCId].append(top)\n",
    "                    SCCIdByNode[top] = SCCId\n",
    "                    if top == cur:\n",
    "                        break\n",
    "                SCCId += 1\n",
    "\n",
    "        dfsId = 0\n",
    "        order, low = [Tarjan.INF] * n, [Tarjan.INF] * n\n",
    "\n",
    "        visited = [False] * n\n",
    "        stack = []\n",
    "        inStack = [False] * n\n",
    "\n",
    "        SCCId = 0\n",
    "        SCCGroupById = [[] for _ in range(n)]\n",
    "        SCCIdByNode = [-1] * n\n",
    "\n",
    "        for cur in range(n):\n",
    "            if not visited[cur]:\n",
    "                dfs(cur)\n",
    "\n",
    "        return SCCId, SCCGroupById, SCCIdByNode\n",
    "\n",
    "    @staticmethod\n",
    "    def getCuttingPointAndCuttingEdge(\n",
    "        n: int, adjMap: DefaultDict[int, Set[int]]\n",
    "    ) -> Tuple[List[int], List[Tuple[int, int]]]:\n",
    "        \"\"\"Tarjan求解无向图的割点和割边(桥)\n",
    "\n",
    "        Args:\n",
    "            n (int): 结点0-n-1\n",
    "            adjMap (DefaultDict[int, Set[int]]): 图\n",
    "\n",
    "        Returns:\n",
    "            Tuple[List[int], List[Tuple[int, int]]]: 割点、桥\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(cur: int, parent: int) -> None:\n",
    "            if visited[cur]:\n",
    "                return\n",
    "            visited[cur] = True\n",
    "\n",
    "            nonlocal dfsId\n",
    "            order[cur] = low[cur] = dfsId\n",
    "            dfsId += 1\n",
    "\n",
    "            dfsChild = 0\n",
    "            for next in adjMap[cur]:\n",
    "                if next == parent:\n",
    "                    continue\n",
    "                if not visited[next]:\n",
    "                    dfsChild += 1\n",
    "                    dfs(next, cur)\n",
    "                    low[cur] = min(low[cur], low[next])\n",
    "                    if low[next] > order[cur]:\n",
    "                        cuttingEdge.append((cur, next))\n",
    "                    if parent != -1 and low[next] >= order[cur]:\n",
    "                        cuttingPoint.add(cur)\n",
    "                    elif parent == -1 and dfsChild > 1:\n",
    "                        cuttingPoint.add(cur)\n",
    "                else:\n",
    "                    low[cur] = min(low[cur], order[next])\n",
    "\n",
    "        dfsId = 0\n",
    "        order, low = [Tarjan.INF] * n, [Tarjan.INF] * n\n",
    "        visited = [False] * n\n",
    "\n",
    "        cuttingPoint = set()\n",
    "        cuttingEdge = []\n",
    "\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                dfs(i, -1)\n",
    "\n",
    "        return list(cuttingPoint), cuttingEdge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        if n == 2:#如果只有两点，两点一线必然是关键边\n",
    "            return connections\n",
    "        def dfs(x):#深搜，寻找两点之间是否相通\n",
    "            if x == j:#如果到达终点\n",
    "                return True\n",
    "            for y in d.get(x, []):\n",
    "                if degree[y] > 1 and (x, y) != (i, j) and visit[y] == 0:#不需要走链，且不能起点和终点直连且下个点未到达过\n",
    "                    visit[y] = 1\n",
    "                    if dfs(y):\n",
    "                        return True\n",
    "            return False\n",
    "        res = []\n",
    "        degree = [0 for i in range(n)]#边数\n",
    "        d = {}#每个点能到达的其他点列表\n",
    "        for i, j in connections:\n",
    "            if i not in d:\n",
    "                d[i] = set()\n",
    "            if j not in d:\n",
    "                d[j] = set()\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "            degree[i] += 1#边+1\n",
    "            degree[j] += 1#边+1\n",
    "        deq = collections.deque()#bfs队列\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:#如果为1，则是链头\n",
    "                deq.append(i)\n",
    "        while deq:\n",
    "            i = deq.popleft()\n",
    "            for j in d[i]:\n",
    "                if degree[j] > 1:\n",
    "                    res.append([i, j])#加入关键边\n",
    "                    degree[j] -= 1#边数减1\n",
    "                    if degree[j] == 1:#如果链未入环，继续遍历\n",
    "                        deq.append(j)\n",
    "        for i, j in connections:\n",
    "            if (degree[i] == 3 and degree[j] >= 3) or (degree[j] == 3 and degree[i] >= 3):#如果满足上面的两个条件\n",
    "                visit = [0 for i in range(n)]\n",
    "                if not dfs(i):#深搜判断是否为关键边\n",
    "                    res.append([i, j])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        def tj(u,f):\n",
    "            dfn[u]=low[u]=self.t\n",
    "            self.t += 1\n",
    "            for v in nxt[u]:\n",
    "                if v not in dfn:\n",
    "                    tj(v,u)\n",
    "                    low[u] = min(low[u],low[v])\n",
    "                    if low[v]>dfn[u]:\n",
    "                        res.append((u,v))\n",
    "                elif v!=f:\n",
    "                    low[u] = min(low[u],dfn[v])\n",
    "        nxt = defaultdict(list)\n",
    "        for u,v in connections:\n",
    "            nxt[u].append(v)\n",
    "            nxt[v].append(u)\n",
    "        self.t = 0\n",
    "        res = []\n",
    "        dfn, low = {},{}\n",
    "        tj(0,-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        if n == 2:#如果只有两点，两点一线必然是关键边\n",
    "            return connections\n",
    "        def dfs(x):#深搜，寻找两点之间是否相通\n",
    "            if x == j:#如果到达终点\n",
    "                return True\n",
    "            for y in d.get(x, []):\n",
    "                if degree[y] > 1 and (x, y) != (i, j) and visit[y] == 0:#不需要走链，且不能起点和终点直连且下个点未到达过\n",
    "                    visit[y] = 1\n",
    "                    if dfs(y):\n",
    "                        return True\n",
    "            return False\n",
    "        res = []\n",
    "        degree = [0 for i in range(n)]#边数\n",
    "        d = {}#每个点能到达的其他点列表\n",
    "        for i, j in connections:\n",
    "            if i not in d:\n",
    "                d[i] = set()\n",
    "            if j not in d:\n",
    "                d[j] = set()\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "            degree[i] += 1#边+1\n",
    "            degree[j] += 1#边+1\n",
    "        deq = collections.deque()#bfs队列\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:#如果为1，则是链头\n",
    "                deq.append(i)\n",
    "        while deq:\n",
    "            i = deq.popleft()\n",
    "            for j in d[i]:\n",
    "                if degree[j] > 1:\n",
    "                    res.append([i, j])#加入关键边\n",
    "                    degree[j] -= 1#边数减1\n",
    "                    if degree[j] == 1:#如果链未入环，继续遍历\n",
    "                        deq.append(j)\n",
    "        for i, j in connections:\n",
    "            if (degree[i] == 3 and degree[j] >= 3) or (degree[j] == 3 and degree[i] >= 3):#如果满足上面的两个条件\n",
    "                visit = [0 for i in range(n)]\n",
    "                if not dfs(i):#深搜判断是否为关键边\n",
    "                    res.append([i, j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        edges = collections.defaultdict(list)\n",
    "        for s, t in connections:\n",
    "            edges[s].append(t)\n",
    "            edges[t].append(s)\n",
    "        parent = [-1] * n \n",
    "        dfn = [-1] * n \n",
    "        low = [-1] * n \n",
    "        ccp = []\n",
    "        stack = []\n",
    "        bridge = []\n",
    "        point = []\n",
    "        def tarjan(node, par, time):\n",
    "            dfn[node] = time \n",
    "            low[node] = time \n",
    "            stack.append(node)\n",
    "            size = 0\n",
    "            for nei in edges[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                if dfn[nei] == -1:\n",
    "                    tarjan(nei, node, time + 1)\n",
    "                    size += 1 \n",
    "                    parent[nei] = node\n",
    "                    if (parent[node] == - 1 and size > 1) or low[nei] >= dfn[node]:\n",
    "                        point.append(node) \n",
    "                    if low[nei] > dfn[node]:\n",
    "                        bridge.append([node, nei])\n",
    "                    low[node] = min(low[node], low[nei])\n",
    "                else:\n",
    "                    low[node] = min(low[node], dfn[nei])\n",
    "            if dfn[node] == low[node]:\n",
    "                ccp.append([])\n",
    "                while stack and stack[-1] != node:\n",
    "                    ccp[-1].append(stack.pop())\n",
    "                ccp[-1].append(stack.pop())\n",
    "        tarjan(0, - 1, 0)\n",
    "        print(point)\n",
    "        print(ccp)\n",
    "        return bridge"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        def check_graph(edge, n):\n",
    "            # edge: 边连接关系 [[],..] n:节点数\n",
    "\n",
    "            # 访问序号与根节点序号\n",
    "            visit = [0] * n\n",
    "            root = [0] * n\n",
    "            # 割点\n",
    "            cut_node = []\n",
    "            # 割边\n",
    "            cut_edge = []\n",
    "            # 强连通分量子树\n",
    "            sub_group = []\n",
    "\n",
    "            # 中间变量\n",
    "            stack = []\n",
    "            index = 1\n",
    "            in_stack = [0] * n\n",
    "\n",
    "            def tarjan(i, father):\n",
    "                nonlocal index\n",
    "                visit[i] = root[i] = index\n",
    "                index += 1\n",
    "                stack.append(i)\n",
    "\n",
    "                in_stack[i] = 1\n",
    "                child = 0\n",
    "                for j in edge[i]:\n",
    "                    if j != father:\n",
    "                        if not visit[j]:\n",
    "                            #当前子节点数加一\n",
    "                            child += 1\n",
    "                            tarjan(j, i)\n",
    "                            x, y = root[i], root[j]\n",
    "                            root[i] = x if x < y else y\n",
    "                            # 割边 low[i] < dfn[i]\n",
    "                            if visit[i] < root[j]:\n",
    "                                cut_edge.append(sorted([i, j]))\n",
    "                            # 两种情况下才为割点 low[i] <= dfn[i]\n",
    "                            if father != -1 and visit[i] <= root[j]:\n",
    "                                cut_node.append(i)\n",
    "                            elif father == -1 and child >= 2:\n",
    "                                cut_node.append(i)\n",
    "                        elif in_stack[j]:\n",
    "                            x, y = root[i], visit[j]\n",
    "                            root[i] = x if x < y else y\n",
    "\n",
    "                if root[i] == visit[i]:\n",
    "                    lst = []\n",
    "                    while stack[-1] != i:\n",
    "                        lst.append(stack.pop())\n",
    "                        in_stack[lst[-1]] = 0\n",
    "                    lst.append(stack.pop())\n",
    "                    in_stack[lst[-1]] = 0\n",
    "                    r = min(root[ls] for ls in lst)\n",
    "                    for ls in lst:\n",
    "                        root[ls] = r\n",
    "                    lst.sort()\n",
    "                    sub_group.append(lst[:])\n",
    "                return\n",
    "\n",
    "            for k in range(n):\n",
    "                if not visit[k]:\n",
    "                    tarjan(k, -1)\n",
    "            cut_edge.sort()\n",
    "            cut_node.sort()\n",
    "            sub_group.sort()\n",
    "            return cut_edge, cut_node, sub_group\n",
    "\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            edges[a].append(b)\n",
    "            edges[b].append(a)\n",
    "        cut_edge, cut_node, sub_group = check_graph(edges, n)\n",
    "        return cut_edge\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        if n == 2:#如果只有两点，两点一线必然是关键边\n",
    "            return connections\n",
    "        def dfs(x):#深搜，寻找两点之间是否相通\n",
    "            if x == j:#如果到达终点\n",
    "                return True\n",
    "            for y in d.get(x, []):\n",
    "                if degree[y] > 1 and (x, y) != (i, j) and visit[y] == 0:#不需要走链，且不能起点和终点直连且下个点未到达过\n",
    "                    visit[y] = 1\n",
    "                    if dfs(y):\n",
    "                        return True\n",
    "            return False\n",
    "        res = []\n",
    "        degree = [0 for i in range(n)]#边数\n",
    "        d = {}#每个点能到达的其他点列表\n",
    "        for i, j in connections:\n",
    "            if i not in d:\n",
    "                d[i] = set()\n",
    "            if j not in d:\n",
    "                d[j] = set()\n",
    "            d[i].add(j)\n",
    "            d[j].add(i)\n",
    "            degree[i] += 1#边+1\n",
    "            degree[j] += 1#边+1\n",
    "        deq = collections.deque()#bfs队列\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:#如果为1，则是链头\n",
    "                deq.append(i)\n",
    "        while deq:\n",
    "            i = deq.popleft()\n",
    "            for j in d[i]:\n",
    "                if degree[j] > 1:\n",
    "                    res.append([i, j])#加入关键边\n",
    "                    degree[j] -= 1#边数减1\n",
    "                    if degree[j] == 1:#如果链未入环，继续遍历\n",
    "                        deq.append(j)\n",
    "        for i, j in connections:\n",
    "            if (degree[i] == 3 and degree[j] >= 3) or (degree[j] == 3 and degree[i] >= 3):#如果满足上面的两个条件\n",
    "                visit = [0 for i in range(n)]\n",
    "                if not dfs(i):#深搜判断是否为关键边\n",
    "                    res.append([i, j])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n",
    "        graph = collections.defaultdict(set)\n",
    "        for edge in connections:\n",
    "            graph[edge[0]].add(edge[1])\n",
    "            graph[edge[1]].add(edge[0])\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        dfn = [-1] * n\n",
    "        low = [-1] * n\n",
    "\n",
    "        def dfs(last, now, depth):\n",
    "            dfn[now] = depth\n",
    "            low[now] = depth\n",
    "            for nxt in graph[now]:\n",
    "                if nxt == last:\n",
    "                    continue\n",
    "                if dfn[nxt] == -1:\n",
    "                    dfs(now, nxt, depth + 1)\n",
    "                    if dfn[now] < low[nxt]:\n",
    "                        ans.append([now, nxt])\n",
    "                low[now] = min(low[now], low[nxt])\n",
    "\n",
    "        dfs(-1, 0, 1)\n",
    "\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
